#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, dist[50005], viz[50005];
bool used[50005];
queue <int> q;
vector < pair <int, int> > g[50005];

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({y, c});
    }
    for (int i = 2; i <= n; ++i)
        dist[i] = 1e9;
    q.push(1);
    while (!q.empty()) {
        int nod = q.front();
        used[nod] = false;
        q.pop();
        ++viz[nod];
        if (viz[nod] == n) {
            fout << "Ciclu negativ!";
            return 0;
        }
        for (int i = 0; i < g[nod].size(); ++i) {
            int next = g[nod][i].first, c = g[nod][i].second;
            if (dist[nod] + c < dist[next]) {
                if (!used[next]) {
                    q.push(next);
                    used[next] = true;
                }
                dist[next] = dist[nod] + c;
            }
        }
    }
    for (int i = 2; i <= n; ++i)
        fout << dist[i] << " ";
    return 0;
}