#!/usr/bin/env python3

import collections, sys

sys.stdout = open('bellmanford.out', 'w')

with open('bellmanford.in', 'r') as f:
    readInts = lambda: map(int, f.readline().split())

    N, M = tuple(readInts())
    edges = [[] for _ in range(N)]

    for _ in range(M):
        A, B, C = tuple(readInts())
        edges[A - 1].append((B - 1, C))

    D, Q, inQ, cnt, negCycle = [sys.maxsize] * N, collections.deque([0]), [False] * N, [0] * N, False
    inQ[0], D[0], cnt[0] = True, 0, 1

    while Q and not negCycle:
        node = Q.popleft()
        inQ[node] = False
        for B, C in edges[node]:
            if D[node] + C < D[B]:
                D[B] = D[node] + C
                if not inQ[B]:
                    Q.append(B)
                    inQ[B] = True
                    cnt[B] += 1
                    if cnt[B] > N:
                        negCycle = True
                        break

    if negCycle:
        print('Ciclu negativ!')
    else:
        print(' '.join(str(x if x != sys.maxsize else 0) for i, x in enumerate(D) if i > 0))