if __name__== "__main__":
    with open( "bellmanford.in","r") as f:
        n, m = map(int, f.readline().strip().split())
        muchii=[]
        for i in range(m):
            x, y,c = map(int, f.readline().strip().split())
            muchii.append((x,y,c))
        dist=[float("inf")] * (n+1)
        dist[1]=0
        for  _ in range(n-1):
            for x, y, c in muchii:
                if dist[x] != float("inf") and dist[x] + c<dist[y]:
                    dist[y]= dist[x]+ c
        ng_cycle=False
        for x, y, c in muchii:
                if dist[x] != float("inf") and dist[x] + c<dist[y]:
                    ng_cycle=True
                    break
        with open ("bellmanford.out", "w") as f:
            if ng_cycle:
                f.write("Ciclu negativ!")
            else:
                dist.pop(1)
                dist.pop(0)
                for el in dist:
                    f.write(str(el) + " ")