#include<cstdio>
#include<vector>
#include<queue>

#define INF 0x3f3f3f3f
#define NMAX 50005

FILE *f=fopen("bellmanford.in","r");
FILE *g=fopen("bellmanford.out","w");

using namespace std;

vector< pair<int,int> > G[NMAX];
bool used[NMAX];
int dist[NMAX],nr[NMAX];
queue<int> Q;
int n,m;
bool ok=true;

void read( void )
{
    fscanf(f,"%d%d",&n,&m);
    for(int i(1); i <= m ; ++i )
    {
        int node1,node2,cost;
        fscanf(f,"%d%d%d",&node1,&node2,&cost);
        G[node1].push_back(make_pair(node2,cost));
    }
    fclose(f);



}
void Bellman_Ford( void )
{
    for(int i(1) ; i <= n ; dist[i++]=INF);
     vector < pair<int,int> > ::iterator it;
    dist[1]=0;
     Q.push(1);
     used[1]=1;
     while(!Q.empty())
     {
         int node=Q.front();
         Q.pop();
         used[node]=0;
         for(it=G[node].begin(); it!=G[node].end();++it )
         {
             int newnode=(*it).first;
             int cost=(*it).second;
             if(dist[newnode]>dist[node] + cost )
             {
                 dist[newnode]=dist[node]+cost;
                 if(!used[newnode])
                 {
                     used[newnode]=1;
                     Q.push(newnode);
                     ++nr[newnode];
                     if(nr[newnode]>n)
                        {ok=false;break;}
                 }



             }



         }



     }


}
void write( void )
{


    if(ok==false)
    fprintf(g,"Ciclue negativ!");
    else
        for(int i(2); i <= n ; ++i)
        fprintf(g,"%d ",dist[i]);
    fclose(g);

}



int main ( void )
{
    read();
    Bellman_Ford();

    write();
    return 0;
}