#include <bits/stdc++.h>
using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct node{
    int value,cost;
};

int  costs[50005], repeat[50005];
vector < pair<int, int> > graf[50005];
queue < node > heap;


int main() {
    int n, m;
    fin >> n >> m;
    for(int i = 1;i <=n; ++i )
        costs[i] = 99999999;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, costsn;
        fin >> x >> y >> costsn;
        graf[x].push_back({y,costsn});
    }
    costs[1] = 0;
    heap.push({1,0});
    bool cicluneg = false;
    while(!heap.empty() and !cicluneg)
    {
        node curent;
        curent.value = heap.front().value;
        curent.cost = heap.front().cost;
        heap.pop();
        if(curent.cost != costs[curent.value])continue;
        for(auto x : graf[curent.value])
        {
                if (costs[x.first] > costs[curent.value] + x.second) {
                    costs[x.first] = min(costs[x.first], costs[curent.value] + x.second);
                    if(repeat[x.first] > n)
                        cicluneg = true;
                    else {
                        heap.push({x.first, costs[x.first]});
                        repeat[x.first]++;
                }
            }
        }
    }
    if(!cicluneg) {
        for (int i = 2; i <= n; ++i)
            if (costs[i] == 99999999)
                fout << 0 << " ";
            else
                fout << costs[i] << " ";
    }
    else fout << "Ciclu negativ!\n";
    return 0;
}