/*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 nod1, nod2, cost;
};
vector<muchie> edges;
vector<int> dist(NMAX, INF);

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

    for (int relaxation = 1; relaxation<=n; relaxation++) {
        bool changed = 0;
        for (auto it: edges) {
            int nod1 = it.nod1, nod2 = it.nod2, cost = it.cost;
            if (dist[nod1] != INF && dist[nod1] + cost < dist[nod2]) {
                if (relaxation == n) { //un lant poate avea maxim n-1 muchii
                    fout << "Ciclu negativ!";
                    return 0;
                }
                dist[nod2] = dist[nod1] + cost;
                changed = 1;
            }
        }
        if (!changed) break; //am ajuns la drumurile optime
    }
    
    for (int i = 2; i<=n; i++) {
        fout << dist[i] << ' ';
    }
    
    return 0;
}