#include <bits/stdc++.h>
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int N=5e4+5,M=2534+5,INF=INFINITY,NINF=-1*INF;

struct graf
{
    int from,to,cost;

} v[M];
int dist[N];

bool bford(int n,int m)
{
    for(int i=2;i<=n;i++) dist[i]=INF;
    dist[1]=0;

    for(int l=1; l<n; l++)
        for(int i=1; i<=m; i++)
            if(dist[v[i].from]+v[i].cost < dist[v[i].to])
                dist[v[i].to]=dist[v[i].from]+v[i].cost;

    for(int i=1; i<=m; i++)
        if(dist[v[i].from]+v[i].cost < dist[v[i].to])
            return 1;

    return 0;
}
int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1; i<=m; i++)
        in>>v[i].from>>v[i].to>>v[i].cost;

    if(bford(n,m))
    {
        out<<"Ciclu negativ!";
        return 0;
    }

    for(int i=2; i<=n; i++)
        out<<dist[i]<<' ';

    return 0;
}