#include <bits/stdc++.h>

using namespace std;
long long seed = chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rng(seed);
const int N = 5e4, inf = 2e9;
int d[N + 5];
vector <pair <int, int>> g[N + 5];
bool inq[N + 5];
long long randhash[N + 5], hashd[N + 5];

int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, u, v, w;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> u >> v >> w,
        g[u].emplace_back(v, w);
    queue <int> q;
    fill(d + 2, d + n + 1, inf);
    for(int i = 1; i <= n; i++)
        randhash[i] = rng();
    hashd[1] = 1;
    unordered_map <long long, int> vis;
    for(q.push(1); !q.empty(); q.pop()) {
        int u = q.front();
        if(++vis[hashd[u]] > 1) {
            cout << "Ciclu negativ!";
            return 0;
        }
        inq[u] = false;
        for(auto [v, w] : g[u]) if(d[v] > d[u] + w) {
            d[v] = d[u] + w;
            hashd[v] = hashd[u] ^ randhash[v];
            if(!inq[v]) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
    for(int i = 2; i <= n; i++)
        cout << d[i] << " ";
    return 0;
}