#include<fstream>
#include<queue>
#define Nmax 50001
#define INF 99999999
using namespace std;
int N,M,S,D[Nmax],AP[Nmax],cn;
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;
    while(M--)
    {
        scanf("%d %d %d",&i,&j,&c);
        adaug(i,j,c);
    }
}
void BeFo()
{
     AP[1]=1; U[1]=1;
     for(int i=2;i<=N;++i) D[i]=INF,AP[i]=0;
     Q.push(1);
     cn=1;
     while(!Q.empty()&&cn)
     {
         int nod=Q.front();
         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);
                    AP[p->nod]++;
                }
                else if(AP[p->nod]>N) cn=0;
            }
     }
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    BeFo();
    if(!cn) printf("Ciclu negativ!\n");
    else
    {
        for(int i=2;i<=N;++i) printf("%d ",D[i]);
        printf("\n");
    }
    return 0;
}