def main():
    with open('bellmanford.in') as fp:
        n, m = list(map(int, fp.readline().split()))
        adj_list = { i+1: [] for i in range(n) }
        dist = [0x7F7F7F7F, ] * (n + 1)
        edges = []

        for line in fp:
            u, v, w = list(map(int, line.split()))
            adj_list[u].append((v, w))
            edges.append((u, v, w))

        dist[1] = 0
        q = [1, ]

        while q:
            u = q.pop(0)
            for v, w in adj_list[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    q.append(v)

        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                print('Ciclu negativ!', file=open('bellmanford.out', 'w'))
                return

        print(' '.join(str(x) for x in dist[2:n + 1]),
              file=open('bellmanford.out', 'w'))

if __name__ == '__main__':
    main()