#include <fstream>
#include <vector>

using namespace std;

const int INF = 2000000000;

vector< pair<int,int> > l[50005];
vector< pair<int,int> >::iterator it;

int n,m,i,p,u,x,nod,y,cost;

bool ok[50005];

int c[1000005],d[50005],ap[50005];

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    for(i=1;i<=m;i++) {
        f>>x>>y>>cost;
        l[x].push_back(make_pair(y,cost));
    }
    p=u=1;
    c[1]=1;
    for(i=2;i<=n;i++)
        d[i]=INF;
    ok[1]=1;
    while(p<=u) {
        ok[c[p]]=0;
        nod=c[p];
        for(it=l[nod].begin();it!=l[nod].end();it++)
            if(d[it->first]>d[nod]+it->second) {
                d[it->first]=d[nod]+it->second;
                ap[it->first]++;
                if (ap[it->first] == n) {
                    g<<"Ciclu negativ!";
                    return 0;
                }
                if(ok[it->first]==0) {
                    ok[it->first]=1;
                    u++;
                    c[u]=it->first;
                }
            }
        p++;
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    g<<"\n";
    return 0;
}