/*
 * 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<vector<pair<int, int>>> adjList;
vector<int> dist, parrent;

void init(){
    s = 1;
    adjList.resize(V+1);
    dist.resize(V+1);
    parrent.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;
        adjList[u].emplace_back(v, c);
    }
}

bool bellmanFord(){
    for(int i = 1; i <= V-1; i++) {
        for (int u = 1; u <= V; u++) {
            for (auto node: adjList[u]) {
                int v, cost;
                v = node.first;
                cost = node.second;
                if (dist[u] + cost < dist[v]) {
                    dist[v] = dist[u] + cost;
                    parrent[v] = u;
                }
            }
        }
    }
    for (int u = 1; u <= V; u++) {
        for (auto node: adjList[u]) {
            int v, cost;
            v = node.first;
            cost = node.second;
            if (dist[u] + cost < 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;
}