#include <iostream>
#include <fstream>
#define L 50005
#define M 250005
#define INF 99999999
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int viz[L], t[3][M * 2], n, m, cst, c[L], p, k, start[L], pi, ps, cost[L], x, y, fr[L], ok;

int ford(int p)
{
    int x;
    pi = ps = 1;
    c[pi] = p;
    viz[p] = 1;
    while(ps <= pi)
    {
        x = start[c[ps]];
        viz[c[ps]] = 0;
        while(x)
        {
            if(cost[c[ps]] + t[2][x] < cost[t[0][x]])
            {
                cost[t[0][x]] = cost[c[ps]] + t[2][x];
                fr[t[0][x]]++;
                if(fr[t[0][x]] > n)
                    return 0;
                if(!viz[t[0][x]])
                {
                    c[++pi] = t[0][x];
                    viz[t[0][x]] = 1;
                }
            }
            x = t[1][x];
        }
        ps++;
    }
    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];
        start[x] = k;
        t[2][k] = cst;
    }
    for(int i = 1; i <= n; i++)
        cost[i] = 1e0;
    cost[1] = 0;
    ok = ford(1);
    if(ok)
    for(int i = 2; i <= n; i++)
        if(cost[i] == INF)
            g << -1 << " ";
        else
            g << cost[i] << " ";
    else
        g << "Ciclu negativ!";

    return 0;
}