#include<bits/stdc++.h>
using namespace std;
ifstream F("bellmanford.in");
ofstream G("bellmanford.out");
int n,m,c[50100],b[50100],i,x,y,d;
queue<int> q;
vector<pair<int,int> > v[50100];
int main()
{
    for(F>>n>>m;m--;F>>x>>y>>d,v[x].push_back({y,d}));
    for(i=2;i<=n;c[i]=1<<30,++i);
    for(q.push(1);!q.empty();) {
        x=q.front(),q.pop(),++b[x];
        if(b[x]>=n)
            return G<<"Ciclu negativ!",0;
        for(auto y:v[x])
            if(c[y.first]>c[x]+y.second)
                c[y.first]=c[x]+y.second,q.push(y.first);
    }
    for(i=2;i<=n;G<<c[i]<<' ',++i);
    return 0;
}