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)