37 lines
No EOL
720 B
Python
37 lines
No EOL
720 B
Python
import sys
|
|
data = sys.stdin.read().split()
|
|
if not data:
|
|
exit()
|
|
n = int(data[0])
|
|
m = int(data[1])
|
|
U = [0] * m
|
|
V = [0] * m
|
|
W = [0] * m
|
|
idx = 2
|
|
for i in range(m):
|
|
U[i] = int(data[idx])
|
|
V[i] = int(data[idx+1])
|
|
W[i] = int(data[idx+2])
|
|
idx += 3
|
|
INF = 10**15
|
|
D = [INF] * (n + 1)
|
|
D[1] = 0
|
|
for _ in range(n - 1):
|
|
any_relaxed = False
|
|
for i in range(m):
|
|
u = U[i]
|
|
if D[u] != INF:
|
|
v = V[i]
|
|
cost = D[u] + W[i]
|
|
if cost < D[v]:
|
|
D[v] = cost
|
|
any_relaxed = True
|
|
if not any_relaxed:
|
|
break
|
|
ans = []
|
|
for i in range(1, n + 1):
|
|
if D[i] == INF:
|
|
ans.append(30000)
|
|
else:
|
|
ans.append(D[i])
|
|
print(*ans) |