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

using namespace std;

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

struct edge{
    edge(int u, int v, int c){
        this->u = u;
        this->v = v;
        this->c = c;
    }
    int u, v, c;
};

int V, E, s;
vector<edge*> edges;
vector<int> dist;

void init(){
    s = 1;
    dist.resize(V+1, 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(new edge(u, v, c));
    }
    in.close();
}

bool bellmanFord(){
    for(int i = 0; i < V-1; i++){
        for(auto edge: edges){
            int u, v, c;
            u = edge->u;
            v = edge->v;
            c = edge->c;
            dist[v] = min(dist[v], dist[u]+c);
        }
    }
    for(auto edge: edges){
        int u, v, c;
        u = edge->u;
        v = edge->v;
        c = edge->c;
        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] << ' ';
    }
    out.close();
    return 0;
}