#include <bits/stdc++.h>
#define Inf (int)(1<<30)

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

int n,m;
int vf[250001],urm[250001],last[50001],nr;
int cost[250001],used[250001];
int dist[50001];
int start=1;
queue <int> c;

void adauga(int nod,int vec,int pret)
{
    vf[++nr]=vec;
    urm[nr]=last[nod];
    last[nod]=nr;
    
    cost[nr]=pret;
}

int main()
{
    in>>n>>m;
    
    int i,j,pret;
    for(int k=1;k<=m;k++)
    {
        in>>i>>j>>pret;
        
        adauga(i,j,pret);
    }
    
    for(int i=2;i<=n;i++)
        dist[i]=Inf;
    
    c.push(start);
    bool foundC=false;
    
    while(!c.empty() && !foundC)
    {
        int nod=c.front();
        c.pop();
        
        for(int k=last[nod];k;k=urm[k])
            if( dist[ vf[k] ]>dist[nod]+cost[k] )
            {
                dist[ vf[k] ]=dist[nod]+cost[k];
                used[k]++;
                
                c.push(vf[k]);
                
                if(used[k]>n)
                    foundC=true;
            }
    }
    
    if(foundC)
        out<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            out<<dist[i]<<' ';
    
    return 0;
}