#include <iostream>
#include <fstream>
using namespace std;

struct reb {
       int a,b,c;
       };
       
int main(){
    const int inf=1 << 30;
    ifstream cinr ("bellmanford.in");
    ofstream cour ("bellmanford.out");
    int n,m,t=1;
    cinr >> n;
    cinr >> m;
    reb g[m];
    for(int i=0; i<=m-1; i++){
            cinr >> g[i].a;
            cinr >> g[i].b;
            cinr >> g[i].c;
            }
    int d[n+1], p[n+1];
    d[1]=0; p[1]=0;
    for(int i=2; i<=n; i++){
            p[i]=0;
            d[i]=inf;
            }
for(int j=1; j<=n-1; j++){ 
    if(t==0){ break; }        
    for(int i=0; i<=m-1; i++){
            if(d[g[i].b]>d[g[i].a]+g[i].c){ d[g[i].b]=d[g[i].a]+g[i].c; t=1;}
            else                          { t=0; }
            }
}
    t=1;
    for(int i=0; i<=m-1; i++){
            if(d[g[i].b]>d[g[i].a]+g[i].c){ t=0; break; }
            }
    if(t){
          for(int i=2; i<=n; i++){
                  cour << d[i] << " ";
                  }
          }
    else {
         cour << "Ciclu negativ!"; 
         }
    //cin.ignore(2);
    
    return 0;
    }