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

using namespace std;

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

int V, E, s;
vector<vector<pair<int, int>>> adjList;
vector<int> dist, arcs;

void init(){
    s = 1;
    adjList.resize(V+1);
    dist.resize(V+1, INT_MAX);
    dist[s] = 0;
    arcs.resize(V+1);
}

void read(){
    in >> V >> E;
    init();
    for(int i = 1; i <= E; i++){
        int u, v, w;
        in >> u >> v >> w;
        adjList[u].emplace_back(v, w);
    }
    in.close();
}

bool bellmanFord(){
    vector<bool> inQueue(V+1);
    queue<int> q;
    q.push(s);
    inQueue[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        for(auto edge: adjList[u]){
            int v, w;
            v = edge.first;
            w = edge.second;
            if(dist[u] != INT_MAX and dist[u]+w < dist[v]){
                dist[v] = dist[u]+w;
                if(!inQueue[v]){
                    q.push(v);
                    inQueue[v] = true;
                    arcs[v] = arcs[u]+1;
                    if(arcs[v] > V-1)
                        return false;
                }
            }
        }
    }
    return true;
}

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