#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 50003;
const int M = 250003;
const int inf = 250000005;
int n, m, nr1, vf[M], lst[N], urm[M], cost[M], d[N], q[M*1000], nr[N];
bool viz[N];

void adauga( int x, int y, int c )
{
    nr1++;
    vf[nr1] = y;
    urm[nr1] = lst[x];
    cost[nr1] = c;
    lst[x] = nr1;
}

int main()
{
    int i, x, y, c, poz;
    in >> n >> m;
    for ( i = 1; i <= m; i++ )
    {
        in >> x >> y >>c;
        adauga(x, y, c);
    }
    for ( i = 1; i <= n; i++ )
        d[i] = inf;
    int p, u;
    p = u = 1;
    q[p] = 1;
    viz[1] = true;
    d[1] = 0;
    nr[1]++;
    while( p <= u )
    {
        x = q[p];
        viz[x] = false;
        poz = lst[x];
        while( poz != 0 )
        {
            y = vf[poz];
            c = cost[poz];
            if ( d[y] > d[x] + c )
            {
                if ( viz[y] == false )
                {
                    u++;
                    q[u] = y;
                    nr[y]++;
                    viz[y] = true;
                }
                d[y] = d[x]+c;
                if ( nr[y] == n )
                {
                    out <<"Ciclu negativ!";
                    return 0;
                }
            }
            poz = urm[poz];
        }
        p++;
    }
    for ( i = 2; i <= n; i++ )
        out << d[i]<<' ';
    return 0;
}