/*
 * https://www.infoarena.ro/problema/bellmanford 100p
 * O(V*E)
 */
#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;
void init(){
    s = 1;
    adjList.resize(V+1);
}

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

void bellmanFord(){
    vector<int> d(V+1, INT_MAX), parent(V+1), pathEdge(V+1);
    vector<bool> in_q(V+1);
    queue<int> q;

    d[s] = parent[s] = 0;
    q.push(s);
    in_q[s] = true;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        in_q[u] = false;
        for(const auto & edge: adjList[u]){
            int v = edge.first;
            int w = edge.second;
            if(d[u] < INT_MAX && d[u]+w < d[v]){
                d[v] = d[u]+w;
                parent[v] = u;
                if(!in_q[v]) {
                    q.push(v);
                    in_q[v] = true;
                    pathEdge[v] = pathEdge[u]+1;
                    if(pathEdge[v] > V-1) {
                        out << "Ciclu negativ!";
                        return;
                    }
                }
            }
        }
    }
    for(int u = 1; u <= V; u++){
        if(u == s)
            continue;
        if(d[u] == INT_MAX)
            out << 0 << ' ';
        else
            out << d[u] << ' ';
    }
}

int main() {
    read();
    bellmanFord();
    return 0;
}