#include<iostream>
#include<fstream>
const int ii = 1<<30;
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int N,M,d[50005];
struct muchie
{
    int x,y,c;
}m[250000];

int main()
{
    in>>N>>M;
    int i,x,y,c;

    for(i=2;i<=N;++i) d[i]=ii;

    for(i=1;i<=M;++i)
    {
        in>>m[i].x>>m[i].y>>m[i].c;
    }
    int cont,pas=0;
    do
    {
        cont=0;
        for(i=1;i<=M;++i)
        {
            x=m[i].x,y=m[i].y,c=m[i].c;
            if(d[y]>d[x]+c) d[y]=d[x]+c,cont=1;
        }
        pas++;
    }while(cont && pas<=N);
    if(pas>N) out<<"Ciclu negativ!";
    else
    for(i=2;i<=N;++i) out<<d[i]<<' ';
    out<<'\n';
}