#include <iostream>
#include <fstream>
#define inf 65536
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
int c[3000000],inc=1,sf=1,d[50001],viz[50001];
struct nod{
    int vecin;
    int val;
    struct nod *urm;
}*l[50001],*actual;
bool bellmanford(int k){
    c[inc]=k;
    for(int i=1;i<=n;++i)
        d[i]=inf;
    d[k]=0;
    while(inc<=sf){
        actual=l[c[inc]];
        while(actual!=NULL){
            if(actual->val+d[c[inc]]<d[actual->vecin]){
                d[actual->vecin]=actual->val+d[c[inc]];
                ++sf;
                c[sf]=actual->vecin;
                ++viz[actual->vecin];
                if(viz[actual->vecin]==n-1)
                    return false;
            }
            actual=actual->urm;
        }
        inc++;
    }
    return true;
}
int main()
{
    in>>n>>m;
    int x,y,valt;
    for(int i=1;i<=m;++i){
        in>>x>>y>>valt;
        actual=new nod;
        actual->vecin=y;
        actual->urm=l[x];
        actual->val=valt;
        l[x]=actual;
    }
    bool ok=bellmanford(1);
    if(ok==false)
        out<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            out<<d[i]<<" ";
    return 0;
}