#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int n,i,j,m,cost[50005],x,y,z;
struct ha
{
    int x; int y; int cost;
} v[50005];
void init()
{
    cost[1]=0;
    for(int i=2;i<=n;i++) cost[i]=999999999;
}
void rez()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(cost[v[j].x]+v[j].cost<cost[v[j].y])
            {
                cost[v[j].y]=cost[v[j].x]+v[j].cost;
            }
        }
    }
}
int checknegativ()
{
    for(int j=1;j<=m;j++)
    {
        if(cost[v[j].x]+v[j].cost<cost[v[j].y]) return 1;
    }
    return 0;
}
int main()
{
    ///cost negativ sau lant de cost minim ce pleaca din 1
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        v[i].x=x;v[i].y=y;v[i].cost=z;
    }
    init();
    ///vedem daca fiecare muchie optimizeaza costul, facem asta de n ori
    rez();
    if(checknegativ()==1) fout<<"Ciclu negativ!";
    else
    {
        for(i=2;i<=n;i++) fout<<cost[i]<<' ';
    }
    return 0;
}