/*
 * https://www.infoarena.ro/problema/bellmanford
 * Complexity: O(nm)
 */
#include <bits/stdc++.h>

using namespace std;

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

int V, E, s;
vector<pair<int, pair<int, int>>> edges;
vector<int> dist;

void init(){
    s = 1;
    dist.resize(V+1);
    for(auto & it: dist)
        it = INT_MAX;
    dist[s] = 0;
}

void read(){
    in >> V >> E;
    init();
    for(int i = 1; i <= E; i++){
        int u, v, c;
        in >> u >> v >> c;
        edges.push_back({u, {v, c}});
    }
}

bool bellmanFord(){
    for(int i = 0; i < V-1; i++){
        for(auto edge: edges){
            int u, v, c;
            u = edge.first;
            v = edge.second.first;
            c = edge.second.second;
            dist[v] = min(dist[v], dist[u]+c);
        }
    }
    for(auto edge: edges){
        int u, v, c;
        u = edge.first;
        v = edge.second.first;
        c = edge.second.second;
        if(dist[u]+c < dist[v])
            return false;
    }
    return true;
}

int main() {
    read();
    if(!bellmanFord())
        out << "Ciclu negativ!";
    else {
        for (int i = 2; i <= V; i++)
            out << dist[i] << ' ';
    }

    return 0;
}