#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define x first
#define y second
#define mod 1000000007
 
using namespace std;

int n, m, x, y, z, nr[100100], dist[100100];
vector < pair < int, int > > V[100100];
queue < int > Q;
bitset < 100100 > v;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    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(); v[curr] = 0;
        for (auto it : V[curr])
            if (dist[it.first] > dist[curr] + it.second)
            {
                dist[it.first] = dist[curr] + it.second;
                if (!v[it.first])
                {
                    if (nr[it.first] > n) return cout << "Ciclu negativ!", 0;
                    v[it.first] = 1;
                    nr[it.first]++;
                    Q.push(it.first);
                }
            }
    }
    for (int i = 2; i <= n; i++) cout << dist[i] << " ";
    return 0;
}