#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
int n, m, x, y, z, nr[100100], dist[100100];
vector < pair < int, int > > V[100100];
queue < int > Q;
int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> x >> y >> z, V[x].push_back({y, z});
    Q.push(1);
    for (int i = 2; i <= n; i++) dist[i] = 2e9;
    while (Q.size())
    {
        int curr = Q.front(); Q.pop();
        for (auto it : V[curr])
            if (dist[it.x] > dist[curr] + it.y)
            {
					dist[it.x] = dist[curr] + it.y;
                    if (nr[it.x] == n) return cout << "Ciclu negativ!", 0;
                    nr[it.x]++;
                    Q.push(it.x);
            }
    }
    for (int i = 2; i <= n; i++) cout << dist[i] << " ";
}