#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#define MAX_VERTICES 50000
#define oo 0x3f3f3f3f
using namespace std;

class Graph {
private:
    int V;
    int E;
    vector<pair<int,int>> g[MAX_VERTICES + 1];
public:
    void readGraph() {
        ifstream fin("bellmanford.in");
        int x, y, c;
        fin >> V >> E;
        for(int i = 0; i < E; ++i) {
            fin >> x >> y >> c;
            g[x].push_back(make_pair(y, c));
        }
        fin.close();
    }

    void bellmanFord(int startNode) {
        ofstream fout("bellmanford.out");
        vector<int>dist(MAX_VERTICES + 1, oo);
        vector<int>nrViz(MAX_VERTICES + 1, 0);
        vector<bool>inQueue(MAX_VERTICES + 1, false);
        queue<int>q;
        bool cycle = false;
        int node;
        dist[startNode] = 0;
        q.push(startNode);
        while(!q.empty() && !cycle) {
            node = q.front();
            q.pop();
            inQueue[node] = false;
            for(auto i : g[node]) {
                if(dist[i.first] > dist[node] + i.second) {
                    dist[i.first] = dist[node] + i.second;
                    if(!inQueue[i.first]) {
                        q.push(i.first);
                        inQueue[i.first] = true;
                        if(++nrViz[i.first] > V)
                            cycle = true;
                    }
                }
            }
        }
        if(cycle)
            fout << "Ciclu negativ!";
        else
            for(int i = 2; i <= V; ++i)
                fout << dist[i] << " ";
        fout << "\n";
    }
};

int main() {
    Graph G;
    G.readGraph();
    G.bellmanFord(1);
    return 0;
}