#include<fstream>
#include<cstring>
#include<queue>
using namespace std;
const int NM = 50005;
const int INF = 0x3f3f3f3f;

typedef struct lnod{
        int vf,cost;
        struct lnod *next;
        }*Nod;
        
Nod a[NM];
queue<int> Q;
bool viz[NM];
int D[NM],nrq[NM],N,M,cod=0;

void add(int x,int y,int c){
     Nod p = new lnod;
     p->vf = y;
     p->cost = c;
     p->next = a[x];
     a[x] = p;
     }
            
void readdata(){
     ifstream fin("bellmanford.in");
     int i,x,y,z;
     fin>>N>>M;
     for(i=1;i<=M;++i)
      { 
       fin>>x>>y>>z;
       add(x,y,z);
      }
     fin.close();   
     }

void Bellman_Ford(){
    int nod;
    memset(D,INF,sizeof(D));
    D[1] = 0;
    Q.push(1);
    viz[1]=1;
    
    while(!Q.empty())
    {
      nod = Q.front();
      Q.pop();
      viz[nod] = 0;
      
      for(Nod p=a[nod];p;p=p->next)
       if(D[nod] + p->cost < D[p->vf])
        {
         D[p->vf] = D[nod] + p->cost;
         if(!viz[p->vf])
          {
            Q.push(p->vf);
            viz[p->vf]=1;
            nrq[p->vf]++;
            if(nrq[p->vf]==N)
             {
               cod = 1;
               return ;
             }          
          }         
        }                                                          
    }   
}

void writedata(){
     ofstream fout("bellmanford.out");
     if(cod)fout<<"Ciclu negativ!";
      else 
       for(int i=2;i<=N;++i)fout<<(D[i]!=INF?D[i]:0)<<' ';
     fout.close();
     }
     
int main(void){
   readdata();
   Bellman_Ford();
   writedata(); 
 return 0;   
}