/*Bellman-Ford - costul minim de la un nod la restul nodurilor*/
/*             - detecteaza daca am cicluri negative*/
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define NMAX 50001
#define INF 1e9
int n, m, start;
struct muchie{
    int nod, cost;
};
vector<muchie> G[NMAX];
vector<int> dist(NMAX, INF), changes(NMAX, 0);

int main() {
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        int a,b,c; fin >> a >> b >> c;
        G[a].push_back({b,c});
    }
    start = 1;
    dist[start] = 0;

    queue<int> Q;
    Q.push(start);
    bool circuitneg = 0;

    while (!Q.empty() && !circuitneg) {
        int nod = Q.front();
        Q.pop();
        for (auto it: G[nod]) {
            int vecin = it.nod, cost = it.cost;
            if (dist[vecin] > dist[nod] + cost) {
                dist[vecin] = dist[nod] + cost;
                changes[vecin]++;
                if (changes[vecin] == n) {
                    circuitneg = 1;
                    break;
                } 
                Q.push(vecin);
            }
        }
    }
    
    if (circuitneg) {
        fout << "Ciclu negativ!\n";
    } else {
        for (int i = 2; i<=n; i++) {
            fout << dist[i] << ' ';
        }
    }
    
    return 0;
}