#include <bits/stdc++.h>
#define N 50005
#define M 250005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

queue<int> c;
int n, m, x, y, cst, k, ok, t[3][N], viz[N], fr[N], cost[N], start[N], om, man;

bool ford(int nod)
{
    c.push(nod);
    viz[1] = 1;
    while(!c.empty())
    {
        om = c.front();
        man = start[om];
        viz[om] = 0;
        while(man)
        {
            if(cost[om] + t[2][man] < cost[t[0][man]])
            {
                cost[t[0][man]] = cost[om] + t[2][man];
                fr[t[0][man]]++;
                if(t[0][man] > n)
                    return 0;
                if(!viz[t[0][man]])
                {
                    c.push(t[0][man]);
                    viz[t[0][man]] = 1;
                }
            }
            man = t[1][man];
        }
        c.pop();
    }
    return 1;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> x >> y >> cst;
        k++;
        t[0][k] = y;
        t[1][k] = start[x];
        t[2][k] = cst;
        start[x] = k;
    }
    for(int i = 1; i <= n; i++)
        cost[i] = 1e9;
    cost[1] = 0;
    ok = ford(1);
    if(ok)
    {
        for(int i = 2; i <= n; i++)
            g << cost[i] << " ";
    }
    else
        g << "Ciclu negativ!";

    return 0;
}