#include <iostream>
#include <fstream>
#define superdumnezeu 1000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct dumnezo
{
    int x,y,w;
};
int dist[100000],pred[100000],i,j,m,n,src=1,k=1;
dumnezo v[100000];
void read()
{
    f>>n>>m;
    for(i=1; i<=m; i++)
        f>> v[i].x >> v[i].y >> v[i].w;
}

void bellman()
{
    for(i=1; i<=n; i++)
        dist[i]=superdumnezeu;
    dist[src]=0;

    for(i=1; i<=n-1; i++)
        for(j=1; j<=m; j++)
            if(dist[v[j].x]+v[j].w < dist[v[j].y])
            {
                dist[v[j].y] = dist[v[j].x]+v[j].w;
                pred[v[j].y] = v[j].x;
            }

    for(i=1; i<=n; i++)
        if(dist[v[i].x] + v[i].w < dist[v[i].y])
            k=0;

    for(i=2; i<=n; i++)
            cout << dist[i] << '\n';
}

void afis()
{
    for(i=2; i<=n; i++)
        g<<dist[i]<<'\n';
}
int main()
{
    read();
    bellman();
    if(k)
        afis();
    else
        g<<"Ciclu negativ!";
    return 0;
}