#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define MAX 0xfffffff

using namespace std;

int d[50001], v[50001];
vector <pair<int, int> > mat[50001];
queue <int> q;
vector <pair<int, int> > :: iterator iv, fv;

int main()
{
    //ifstream in ("date.in");/*
    ifstream in ("bellmanford.in");
    ofstream out ("bellmanford.out");//*/
    int n, m, i, x, y, c;
    in >> n >> m;
    for (i = 0; i < m; ++i) {
        in >> x >> y >> c;
        mat[x].push_back ({y, c});
    }
    for (i = 2; i <= n; ++i) {
        d[i] = MAX;
    }
    q.push(1);
    while (!q.empty()) {
        x = q.front();
        q.pop();
        if (v[x] > n) {out << "Ciclu negativ!"; return 0;}
        v[x]++;
        fv = mat[x].end();
        for (iv = mat[x].begin(); iv != fv; ++iv) {
            if (d[iv->first] > d[x] + iv->second) {
                d[iv->first] = d[x] + iv->second;
                q.push (iv->first);
            }
        }
    }

    for (i = 2; i <= n; ++i) {
        out << d[i] << " ";
    }
    return 0;
}