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

using namespace std;

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

int n,m,i,j,x,y,pret,inc,sf,cost[50001];
vector < tuple <int,int,int> > muchii;

int main()
{
    ios::sync_with_stdio(0);
    f >> n >> m;
    for(i = 0 ; i < m; ++ i)
    {
        f >> x >> y >> pret;
        muchii.push_back(make_tuple(x,y,pret));
    }
    for(i = 1; i <= n; ++ i)
        cost[i] = INF;
    cost[1] = 0;
    for(i = 1; i < n; ++ i)
        for(j = 0 ; j < m; ++ j)
        {
            inc = get<0>(muchii[j]);
            sf = get<1>(muchii[j]);
            pret = get<2>(muchii[j]);
            if(cost[inc] != INF && cost[sf] > cost[inc] + pret)
                cost[sf] = cost[inc] + pret;
        }
    for(i = 0; i < m; ++ i)
    {
        inc = get<0>(muchii[i]);
        sf = get<1>(muchii[i]);
        pret = get<2>(muchii[i]);
        if(cost[inc] != INF && cost[sf] > cost[inc] + pret)
        {
            g << "Ciclu negativ!";
            return 0;
        }
    }
    for(i = 2; i <= n; ++ i)
        g << cost[i] << ' ';
}