//#include<iostream.h>
#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;


const int nmax=50000;
const int INF = 0x3f3f3f3f;
int N,M;
vector<pair<int,int> > G[nmax+100];



void citire()
     {freopen("bellmanford.in","r",stdin);
      int i,a,b,c;      
            
      scanf("%d %d",&N,&M);   
      for(i=1;i<=M;i++)
            {scanf("%d %d %d",&a,&b,&c);                 //creez graful din datele  
             G[a].push_back(make_pair(b,c));           //de intrare
             }
      fclose(stdin);
      }
void solveNwrite()
     {queue<int> Q;
      bitset<nmax+100> in_queue(false);  
      vector<int> dist(nmax+100, INF), cnt_in_queue(nmax+100, 0);
      vector<pair<int,int> >::iterator it;
      int nodcur,i;
      bool negative_cycle=false;
      
      dist[1]=0; Q.push(1); in_queue[1].flip(); cnt_in_queue[1]++;
      
      while(!Q.empty() && !negative_cycle)
              {nodcur=Q.front();
               Q.pop();
               in_queue[nodcur].flip();
               for(it=G[nodcur].begin();it!=G[nodcur].end();it++)
                           if(dist[nodcur]+it->second<dist[it->first])
                                 {dist[it->first]=dist[nodcur]+it->second;
                                  if(!in_queue[it->first])
                                               {if(cnt_in_queue[it->first]>N)
                                                       negative_cycle=true;
                                                else
                                                      {Q.push(it->first);
                                                       in_queue[it->first].flip();
                                                       cnt_in_queue[it->first]++;
                                                      }
                                               }
                                 }
              }
              
     freopen("bellmanford.out","w",stdout);
     
     if(negative_cycle)  printf("Ciclu negativ!"); 
     else                for(i=2;i<=N;i++)  printf("%d ",dist[i]);
     printf("\n");  
     fclose(stdout);
     } 
int main()
    {citire();
     solveNwrite();        
     return 0;
    }