#include<fstream>
#include<vector>
#include<queue>
#define maxn 50004
#define inf 55555558
using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");

vector < pair <int,int> > g[maxn];
queue <int> q;
bool este[maxn],t=true;
int d[maxn],nr[maxn];
int nr_vecini,nod;
int i,n,m,x,y,c;

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

    for(i=1;i<=m;i++){
                      fi>>x>>y>>c;
                      g[x].push_back(make_pair(y,c));
                     }
    
    for(i=1;i<=n;i++){ d[i]=inf; este[i]=0; }
                     
    d[1]=0; este[1]=1; q.push(1); 
    
    while(!q.empty() && t)
    {
     nod=q.front();
     q.pop();
     este[nod]=0;
     
     nr_vecini=g[nod].size();
     for(i=0;i<nr_vecini;i++)
       if(d[nod]+g[nod][i].second<d[g[nod][i].first])
          {
           d[g[nod][i].first]=d[nod]+g[nod][i].second;
           if(!este[g[nod][i].first]){
                                      q.push(g[nod][i].first);
                                      este[g[nod][i].first]=1;
                                      nr[g[nod][i].first]++;
                                      
                                      if(nr[g[nod][i].first]>=n) t=false;
                                     } 
          } 
    }
    
    if(!t) fo<<"Ciclu negativ!";
    else for(i=2;i<=n;i++) fo<<d[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}