/*
 * 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{
    int u, v, w;
    Edge(int u, int v, int w){
        this->u = u;
        this->v = v;
        this->w = w;
    }
};

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, w;
        in >> u >> v >> w;
        edges.emplace_back(u, v, w);
    }
    in.close();
}

bool bellmanFord(){
    for(int i = 1; i < V; i++){
        for(auto edge: edges){
            int u, v, w;
            u = edge.u;
            v = edge.v;
            w = edge.w;
            if(dist[u] != INT_MAX && dist[u]+w < dist[v])
                dist[v] = dist[u]+w;
        }
    }
    for(auto edge: edges){
        int u, v, w;
        u = edge.u;
        v = edge.v;
        w = edge.w;
        if(dist[u] != INT_MAX && dist[u]+w < 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;
}