#include <fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int inf=INT_MAX;
struct Edge{
    int x,y,c;
}mu[250004];
int n,m,x,y,c,ok,dist[50004];
void bmf()
{
    for(int i=1;i<=n;i++)
        dist[i]=inf;
    dist[1]=0;
    for(int r=1;r<=n-1;r++)
        for(int i=1;i<=m;i++)
            if(dist[mu[i].y]>dist[mu[i].x]+mu[i].c)
                dist[mu[i].y]=dist[mu[i].x]+mu[i].c;
    for(int i=1;i<=m&&!ok;i++)
        if(dist[mu[i].y]>dist[mu[i].x]+mu[i].c)
            ok=1;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        mu[i].x=x;
        mu[i].y=y;
        mu[i].c=c;
    }
    bmf();
    if(ok)
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<' ';
    return 0;
}