#include <iostream>
#include <fstream>
#define NMAX 50000
#define MMAX 250000
#define INF  250000000
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct edge
{
    int e1,e2,c;
}v[MMAX+5];
int n,m,cost[NMAX+5];

bool BellmanFord()
{
    int i,j,x,y,z;
    for(i=1;i<=n-1;i++)
    {
        for(j=1;j<=m;j++)
        {
            x=v[j].e1;
            y=v[j].e2;
            z=v[j].c;
            if(cost[x]+z<cost[y])
                cost[y]=cost[x]+z;
        }
    }
    for(i=1;i<=m;i++)
    {
        x=v[i].e1;
        y=v[i].e2;
        z=v[i].c;
        if(cost[x]+z<cost[y])
            return false;
    }
    return true;
}

int main()
{
    int i,x,y,z;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        v[i].e1=x;
        v[i].e2=y;
        v[i].c=z;
    }
    for(i=2;i<=n;i++)
        cost[i]=INF;
    if(BellmanFord())
        for(i=2;i<=n;i++)
            out<<cost[i]<<' ';
    else
        out<<"Ciclu negativ!";
    return 0;
}