#include <bits/stdc++.h>
#define maxn 50005
#define maxm 250005
#define mkp make_pair
using namespace std;
struct edge
{
    int info,cost;
    edge *next;
}*graf[maxn];
int n,m,x,y,z,aparitii[maxn];
vector<int>d;
bitset<maxn>in_coada(false);
bool ciclu_negativ;
void add(int p,int q,int z)
{
    edge *v=new edge;
    v->info=q;
    v->cost=z;
    v->next=graf[p];
    graf[p]=v;
}
void bmf(int start)
{
   d[start]=0;
   in_coada[start]=1;
   //aparitii[start]++;
   queue<int>Q;
   Q.push(start);
   while(!Q.empty() && !ciclu_negativ)
   {
       int x=Q.front();Q.pop();
       in_coada[x]=0;
       for(edge *aux=graf[x];aux;aux=aux->next)
           if(d[aux->info]>d[x]+aux->cost)
           {
               d[aux->info]=d[x]+aux->cost;
               if(!in_coada[aux->info])
               {
                   Q.push(aux->info);
                   aparitii[aux->info]++;
                   in_coada[aux->info]=1;
               }
                if(aparitii[aux->info]>n)
                    ciclu_negativ=true;
           }
   }
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    d=vector<int>(n+1,INT_MAX);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&z);
        add(x,y,z);
    }
    bmf(1);
    if(ciclu_negativ==true)
        printf("Ciclu negativ!\n");
    else
        for(int i=2;i<=n;++i)
            printf("%d ",d[i]);
    return 0;
}