#include <stdio.h>
#include <vector>
using namespace std;
#define MAXN 50010
#define INF 1000000000
 
int d[MAXN],f[MAXN];
int N,M,k;
vector<int> C[MAXN], G[MAXN];
int Q[1<<20];
 
void init()
{  
    int i;
    for(i=1;i<=N;i++)
        d[i]=INF;
}
 
void citire()
{
    FILE *fin=fopen("bellmanford.in","r");
    fscanf(fin,"%d %d",&N,&M);
 
    int i,j,t,z;
 
    for(z=1;z<=M;z++)
    {  
        fscanf(fin,"%d %d %d",&i,&j,&t);
        G[i].push_back(j);
        C[i].push_back(t);
 
    }
     
}
 
int bell()
{
    int x,i;
    int inc, sf;
    inc = sf = 0;
    d[1] = 0;
    Q[0] = 1;
    while(inc<=sf)
    {  
        x = Q[inc];
        inc++;
        for(i=0;i<G[x].size();i++)
            if(d[G[x][i]]>d[x]+C[x][i])
				{
					
				d[G[x][i]]=d[x]+C[x][i];
				sf++; 
				Q[sf] = G[x][i];
				f[G[x][i]]++;
				if(f[G[x][i]]==N) {k++; return 0;}
				}  
             
    }  
return 0;    
}
 
void afisare()
{
    int i;
    FILE *fout=fopen("bellmanford.out","w");
     
     
    for(i=2;i<=N;i++)
        fprintf(fout,"%d ",d[i]);
 
 
     
}
 
int main()
{
    citire();
    init();
    bell();
    if (k==0)afisare();
	else	{
			FILE *fout=fopen("bellmanford.out","w");
			fprintf(fout,"Ciclu negativ!");
			}
     
return 0;
}