#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <queue>
#include <climits>
#define INF INT_MAX
using namespace std;

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

const int nmax = 5e4 + 5;
vector <pair <int, int> > v[nmax];
vector <int> cost (nmax, INF);
queue <int> q;
bool used[nmax];
int entrances[nmax], n, m;
void preprocess() {
    fin >> n >> m;
    int x, y, c;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
    }
}

void bellmanford() {
    q.push(1);
    cost[1] = 0;
    used[1] = 1;
    int x;
    while (!q.empty()) {
        x = q.front();
        for (auto it : v[x]) {
            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;
                    }
                }
            }
        }
        q.pop();
        used[x] = 0;
    }
    for (int i = 2; i <= n; ++i)
        fout << cost[i] << " ";
}


int main()
{
    preprocess();
    bellmanford();
    return 0;
}