#include<fstream>
#include<iostream>
#define maxn 500005
#define maxm 2500025
#define infinity 1000001
using namespace std;

long n, m, i, j, dist[maxn], v[maxn][3], x, y, c;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

void bellman_ford()
{for(i=1; i<=n-1; i++)   
    for(j=1; j<=m; j++)
       {x=v[j][0];
        y=v[j][1]; 
        c=v[j][2];
        if(dist[x]+c<dist[y])
          dist[y]=dist[x]+c;     
       }      
}

int is_negative()
{for(i=1; i<=m; i++)
     {x=v[i][0];
      y=v[i][1]; 
      c=v[i][2];
      if(dist[x]+c<dist[y])
        return 1;
     }
return 0;
}

int main()
{f>>n;
f>>m;    

for(i=1; i<=m; i++)
   {f>>x;
    v[i][0]=x;
    f>>y;
    v[i][1]=y;
    f>>c;
    v[i][2]=c;
   }  
   
dist[1]=0;
for(i=2; i<=n; i++) 
   dist[i]=infinity;   

bellman_ford();

if(is_negative()==1)   
   g<<"Ciclu negativ!";
else for(i=2; i<=n; i++)
        g<<dist[i]<<" ";

f.close();
g.close();
return 0;  
}