#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, M = 250000, inf = 2e9;
int d[N + 5];
struct edge {
    int to, weight, id;
    edge(int a, int b, int c) : to(a), weight(b), id(c) {}
};
vector <edge> g[N + 5];
bool inq[N + 5];
long long randhash[M + 5], hashd[N + 5], hashedge[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, i),
        randhash[i] = rng();
    queue <int> q;
    fill(d + 2, d + n + 1, inf);
    hashd[1] = 1;
    for(q.push(1); !q.empty(); q.pop()) {
        int u = q.front();
        inq[u] = false;
        for(auto [v, w, id] : g[u]) if(d[v] > d[u] + w) {
            long long h = randhash[id];
            d[v] = d[u] + w;
            if(hashedge[id] == (hashd[u] ^ h)) {
                cout << "Ciclu negativ!";
                return 0;
            }
            hashedge[id] = hashd[v] = hashd[u] ^ h;
            if(!inq[v]) {
                q.push(v);
                inq[v] = true;
            }
        }
    }
    for(int i = 2; i <= n; i++)
        cout << d[i] << " ";
    return 0;
}