#include <bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int NMAX = 50001, INF = 5e8;
int n, m, dist[NMAX];
vector<array<int, 3>> edges;

bool Bellman(int source)
{
    fill(dist + 1, dist + n + 1, INF);
    dist[source] = 0;
    for(int it = 1; it <= n; it++)
    {
        bool better = false;
        for(auto [u, v, cost] : edges)
        {
            if(dist[v] > dist[u] + cost)
            {
                dist[v] = dist[u] + cost;
                better = true;
            }
        }
        if(!better)
            return false;
        if(it == n && better)
            return true;
    }
    return false;
}

int main()
{
    fin >> n >> m;
    while(m--)
    {
        int u, v, cost;
        fin >> u >> v >> cost;
        edges.push_back({u, v, cost});
    }
    if(Bellman(1))
        fout << "Ciclu negativ!";
    else
        for(int node = 2; node <= n; node++)
            fout << dist[node] << " ";

    fin.close();
    fout.close();
    return 0;
}