#include <fstream>
#define inf 1<<30

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct graf{
    int nod,cost;
    graf *urm;
}*v[50005];
int n,m,use[50005],f[50005],Q[50005],d[50005];
void add(int x, int y, int c){
graf *p=new graf;
p->nod=y;
p->cost=c;
p->urm=v[x];
v[x]=p;
}
void citire(){
    int a,b,c;
    for(;m;m--){
        fin>>a>>b>>c;
        add(a,b,c);
    }
}
void bell(){
int p,u,x;
for(int i=2;i<=n;i++)
    d[i]=inf;
use[1]=Q[1]=1;
p=u=1;
while(p<=u){
    x=Q[p];
    p++;
    use[x]=0;
    for(graf *nou=v[x];nou;nou=nou->urm){
        if(d[nou->nod]>nou->cost+d[x]){
                d[nou->nod]=nou->cost+d[x];
            if(!use[nou->nod]){
                Q[++u]=nou->nod;
                use[nou->nod]=1;
            }
            f[nou->nod]++;
            if(f[nou->nod]==n){
                fout<<"Ciclu negativ!";
                return;
            }
        }
    }
}
    for(int i=2;i<=n;i++)
        fout<<d[i]<<' ';
}
int main()
{
    fin>>n>>m;
    citire();
    bell();
    return 0;
}