#include<fstream>
#include<queue>
#define Nmax 50006
#define INF 999999999
using namespace std;
int N,M,S,D[Nmax],cn,AP[Nmax];
bool U[Nmax];
struct lista{int nod,cost; lista *leg;} *G[Nmax];
queue<int> Q;
void adaug(int i,int j,int c)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->leg=G[i];
    p->cost=c;
    G[i]=p;
}
void citire()
{
    scanf("%d %d",&N,&M);
    int i,j,c;
    for(int k=1;k<=M;k++)
    {
        scanf("%d %d %d",&i,&j,&c);
        adaug(i,j,c);
    }
}
void BeFo()
{
     U[1]=1; D[1]=0;
     for(int i=2;i<=N;++i) D[i]=INF,U[i]=0;
     Q.push(1);
     cn=1;
     while(!Q.empty())
     {
         int nod=Q.front();
         AP[nod]++;
         if(AP[nod]==N)
         {
             cn=0;
             return;
         }
         Q.pop();
         U[nod]=0;
         for(lista *p=G[nod];p;p=p->leg)
            if(D[nod]+p->cost<D[p->nod])
            {
                D[p->nod]=D[nod]+p->cost;
                if(!U[p->nod])
                {
                    U[p->nod]=1;
                    Q.push(p->nod);
                }
            }
     }
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    BeFo();
    if(cn==0) printf("Ciclu negativ!\n");
    else
    {
        for(int i=2;i<=N;++i) printf("%d ",D[i]);
        printf("\n");
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}