#include<fstream>
#include<queue>
#include<vector>
#include<algorithm>
#define MAXN 50001
#define  pb push_back
#define INF 1000000000 
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int N,M,d[MAXN],V[MAXN];
int a,b,c;
vector <int> G[MAXN],C[MAXN]; 
queue<int> q;
int main() {
	int i,j,x;
   cin>>N>>M;
    for(i=1;i<=M;i++)  {
	          cin>>a>>b>>c;
			  G[a].pb(b);
			  C[a].pb(c); }
	for(i=1;i<=N;i++)
	             d[i]=INF;		 		  
       q.push(1);
       d[1]=0;	
       V[1]=1;
       while( q.size()>0) {
         x=q.front();
         q.pop();
         for(j=0;j<G[x].size();j++)
             if(d[x]+C[x][j]<d[G[x][j]]) { 
                           V[G[x][j]]++; 
                           if( V[G[x][j]]==N ) {
						   	         cout<<"Ciclu negativ!";
						   	         return 0;  }	         
                                  d[G[x][j]]=d[x]+C[x][j];
                                  q.push(G[x][j]); 
             }                    
      }//end while 
	for(i=2;i<=N;i++)
	       cout<<d[i]<<" ";                                                                  
	return 0;
}