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

int N,M;

struct elem
{
    int x,y,weight;
};

vector <elem> A;
int D[50004],PRED[50004];

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

void write_data()
{

    for(vector <elem>::iterator it=A.begin();it!=A.end();it++)
            {
                elem e=*it;
                if(D[e.x]+e.weight<D[e.y])
                    {
                        printf("Ciclu negativ!");
                        return;
                    }
            }
    for(int i=2;i<=N;i++)
        printf("%d ",D[i]);

}


void bellman_ford()
{
    for(int i=1;i<=N;i++)
        D[i]=INF,PRED[i]=0;
    D[1]=0;
    for(int i=1;i<=N-1;i++)
         for(vector <elem>::iterator it=A.begin();it!=A.end();it++)
            {
                elem e=*it;
                if(D[e.x]+e.weight<D[e.y])
                    {
                        D[e.y]=D[e.x]+e.weight;
                        PRED[e.y]=e.x;
                    }
            }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read_data();
    bellman_ford();
    write_data();
    return 0;
}