#include <bits/stdc++.h>

using namespace std;

#define nmax 50004
#define INF 0x3f3f3f

bool used[nmax];
vector <int> Cost(nmax, INF);
vector <pair <int, int> > v[nmax];
int entrances[nmax];

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


int main()
{
    int n, m;
    fin >> n >> m;
    int x, y, c;

    for (; m; --m) {
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
    queue <int> q;
    q.push(1);
    used[1] = 1;
    Cost[1] = 0;

    while (!q.empty()) {
        x = q.front();
        for (vector <pair <int, int> > :: iterator it = v[x].begin(); it != v[x].end(); ++it) {
            if (Cost[x] + it->second < Cost[it->first]) {
                Cost[it->first] = Cost[x] + it->second;
                if (!used[it->first]) {
                    q.push(it->first);
                    used[it->first = 1];
                    entrances[it->first]++;
                    if (entrances[it->first] == n) {
                        fout << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
        }
        used[x] = 0;
        q.pop();
    }
    for (int i = 2; i <= n; ++i) {
        fout << Cost[i] << " ";
    }
    return 0;
}