#include <bits/stdc++.h>
#define MAX 500005
#define INF 1000000000
#define pereche pair<int, int>
#define fi first
#define se second
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, x, y, c, i, dist[MAX], f[MAX];
queue<pereche>q;
vector<pereche>v[MAX];
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++) {
        fin>>x>>y>>c;
        v[x].push_back({y, c});
    }
    for (i=2; i<=n; i++) dist[i]=INF;
    q.push({1, 0});
    while (!q.empty()) {
        pereche x=q.front();
        q.pop();
        f[x.fi]++;
        if (f[x.fi]==n+2) {
            fout<<"Ciclu negativ!";
            return 0;
        }
        for (auto y:v[x.fi]) {
            if (dist[y.fi]>x.se+y.se) {
                dist[y.fi]=x.se+y.se;
                q.push({y.fi, dist[y.fi]});
            }
        }
    }
    for (i=2; i<=n; i++) fout<<dist[i]<<' ';
    return 0;
}