#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;


/// v[sursa] = (destinatie, cost)
vector < vector <pair <int, int > > > adj;
///function performs bellmanford on graph
///returns false if the graph has a negative weight cycle
///return true otherwise
///in the vector dist, we find the distances from source to all other nodes of the graph
vector <bool> inQueue;
vector <int> counter;
bool bellmanford(int source, int numberOfNodes, vector <int>& dist, vector <bool>& inQueue, vector <int>& counter) {
    dist.resize(numberOfNodes + 1, INT_MAX);
    inQueue.resize(numberOfNodes + 1);
    counter.resize(numberOfNodes + 1);
    dist[source] = 0;
    inQueue[source] = true;
    counter[source]++;
    queue <int> q;
    q.push(source);
    while(!q.empty()) {
        int src = q.front();
        q.pop();
        inQueue[src] = false;
        for(unsigned int i = 0; i < adj[src].size(); ++i) {
            int cost = adj[src][i].second;
            int dest = adj[src][i].first;
            if(dist[src] != INT_MAX && dist[src] + cost < dist[dest]) {
                dist[dest] = dist[src] + cost;
                if(!inQueue[dest]) {
                    q.push(dest);
                    inQueue[dest] = true;
                    counter[dest] ++;
                }
                if(counter[dest] > numberOfNodes - 1) {
                    return false;
                }
            }
        }
    }

    return true;

}

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m;
    f >> n >> m;
    adj.resize(n + 1);
    for(int i = 0; i < m; ++i) {
        int src, dest, cost;
        f >> src >> dest >> cost;
        adj[src].push_back(make_pair(dest, cost));
    }
    vector <int> dist;
    if(bellmanford(1, n, dist, inQueue, counter)) {
        for(int i = 2; i <= n; ++i) {
            g << dist[i] << " ";
        }
    } else {
        g << "Ciclu negativ!";
    }
    f.close();
    g.close();
    return 0;
}