#include <bits/stdc++.h>
#define NMAX 50005
#define pi pair<int,int>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m, viz[NMAX], dist[NMAX], inQ[NMAX];
vector <pi> G[NMAX];
queue <int> Q;
int BF(int start)
{
    for(int i = 1; i <= n; ++i)
        dist[i] = 1 << 30;
    dist[start] = 0;
    viz[start] = 1;
    inQ[start] = 1;
    Q.push(start);
    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        inQ[nod] = 0;
        for(auto it : G[nod])
        {
            int cost = it.second;
            int next = it.first;
            if(dist[nod] + cost < dist[next])
            {
                dist[next] = dist[nod] + cost;
                viz[next]++;
                if(viz[next] >= n-1) return 0;

                if(!inQ[next])
                {
                    Q.push(next);
                    inQ[next] = 1;
                }
            }
        }
    }
    return 1;
}
int main()
{
    f >> n >> m;
    for(int x, y, c, i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        G[x].push_back({y,c});
    }
    if(!BF(1))
        g << "Ciclu negativ!";
    else
    {
        for(int i = 2; i <= n; ++i)
            if(dist[i] == 1 << 30)
                g << 0 << ' ';
            else
                g << dist[i] << ' ';
    }
    f.close();
    g.close();
    return 0;
}