#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define INF 1000000000
using namespace std;

int N,M;

struct elem
{
    int y,weight;
};

vector <elem> A[50004];
int D[50004], VIZ[50004],CNT[50004];
queue <int>Q;

void read_data()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
        {
            elem E;
            int x;
            scanf("%d%d%d",&x,&E.y,&E.weight);
            A[x].push_back(E);
        }
}


bool bellman_ford()
{
    for(int i=1;i<=N;i++)
        D[i]=INF;
    D[1]=0;
    Q.push(1);
    VIZ[1]=1;
    CNT[1]=1;
    while(!Q.empty())
    {
         int x=Q.front();
         Q.pop();
         VIZ[x]=0;
         for(vector <elem>::iterator it=A[x].begin();it!=A[x].end();it++)
            {
                elem e=*it;
                if(D[x]+e.weight<D[e.y])
                    {
                        D[e.y]=D[x]+e.weight;
                        //PRED[e.y]=e.x;
                        CNT[e.y]++;
                        if(CNT[e.y]>N) return true;
                        if(VIZ[e.y]==0)
                          {
                              Q.push(e.y);
                              VIZ[e.y]=1;

                          }
                    }
            }
    }
    return false;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read_data();
    bool b=bellman_ford();
    if(b)
        printf("Ciclu negativ!");
    else
      for(int i=2;i<=N;i++)
        printf("%d ",D[i]);

    return 0;
}