#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <fstream>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m;
vector<vector<pair<int,int>>> muchii;
vector<int> dist, viz, lung;
queue<int> q;
const int INF = 1e6;
void Bellman(int s) {
    dist.assign(n+1,INF);
    lung.assign(n+1,0);
    viz.assign(n+1,0);
    dist[s]=0;
    viz[s]=1;
    q.push(s);
    while (q.size() != 0) {
        int front = q.front();
        viz[front]=0;
        q.pop();
        for (auto & m : muchii[front]) {
            int nod_m = m.first;
            int cost_m = m.second;
            if (dist[nod_m] > dist[front] + cost_m) {
                dist[nod_m] = dist[front]+cost_m;
                lung[nod_m] = lung[front] + 1;
                if (lung[nod_m] > n-1) {
                    fout<<"Ciclu negativ!";
                    return;
                }
                if (viz[nod_m] == 0) {
                    viz[nod_m]=1;
                    q.push(nod_m);
                }
            }
        }
    }
    for (int i=2;i<=n;i++) fout<<dist[i]<<" ";
}
int main() {
    fin>>n>>m;
    muchii.resize(n+1);
    for (int i=1;i<=m;i++) {
        int a, b, c;
        fin>>a>>b>>c;
        muchii[a].push_back({b,c});
    }
    Bellman(1);
    return 0;
}