#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

struct bellman
{
    int inc,sf,pret;
} v[250005];
int n,m,i,j,cost[50005],a,b,c;
bool ok;

int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    for(i = 0; i < m; ++ i)
    {
        f >> v[i].inc >> v[i].sf >> v[i].pret;
    }
    for(i = 1; i <= n; ++ i)
        cost[i] = INF;
    cost[1] = 0;
    for(i = 1; i < n; ++ i)
    {
        ok = 0;
        for(j = 0; j < m; ++ j)
        {
            a = v[j].inc;
            b = v[j].sf;
            c = v[j].pret;
            if(cost[a] != INF && cost[b] > cost[a] + c)
            {
                cost[b] = cost[a] + c;
                ok = 1;
            }
        }
        if(!ok)
            break;
    }
    for(i = 0; i < m; ++ i)
    {
        a = v[i].inc;
        b = v[i].sf;
        c = v[i].pret;
        if(cost[a] != INF && cost[b] > cost[a] + c)
        {
            g << "Ciclu negativ!";
            return 0;
        }
    }
    for(i = 2; i <= n; ++ i)
        g << cost[i] << ' ';
}