#include <bits/stdc++.h>
#define NMAX 50002
#define INF 999999999

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

bitset <NMAX> inQ;
queue <int> q;
vector <pair<int,int>> v[NMAX];

int N,M;
int d[NMAX],cnt[NMAX];
int x,y,z;
int s = 1;

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> x >> y >> z;
        v[x].push_back(make_pair(y,z));
    }
    fill(d+1, d+N+1, INF);
    d[s] = 0;
    inQ[s] = 1;
    q.push(s);
    while(q.size()) {
        int nod = q.front();
        q.pop();
        inQ[nod] = 0;
        for (auto it:v[nod]) {
            int vec, dvec;
            vec = it.first;
            dvec = it.second;
            if (d[vec] > d[nod] + dvec) {
                d[vec] = d[nod] + dvec;
                cnt[vec]++;
                if (cnt[vec] > N) {
                    fout << "Ciclu negativ!";
                    return 0;
                }
                if (!inQ[vec]) {
                    inQ[vec] = 1;
                    q.push(vec);
                }
            }
        }
    }
    for (int i = 2; i <= N; ++i)
        fout << d[i] << ' ';

    return 0;
}