#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <climits>

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

int n, m, x, y, c, nod, vecin, cost;
int d[10000005], cnt[10000005], inQ[10000005];
const int N_MAX = 100005;
queue<int> Q;
vector <pair<int, int>> L[10000005];

int main()
{
    fin>>n>>m;
    int s=1;
    for(int i=1;i<=m;i++){
        fin>> x >> y >> c;
        L[x].push_back({y, c});
    }

    for(int i=1;i<=n;i++){
        d[i]= INT_MAX;
    }

    d[s]=0;
    inQ[s]=1;
    cnt[s]=1;
    Q.push(s);
    while(!Q.empty()) {
        nod = Q.front();
        Q.pop();
        inQ[nod]=0;
        for(auto muchie : L[nod]){
            vecin = muchie.first;
            cost = muchie.second;
            if(d[vecin] > d[nod] + cost && d[nod] != INT_MAX){
                d[vecin] = d[nod] + cost;
                if(inQ[vecin]==0){
                    inQ[vecin] = 1;
                    Q.push(vecin);
                    cnt[vecin]++;
                    if(cnt[vecin] > n){
                        fout<<"Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i=2; i<=n ;i++){
        if(d[i] == INT_MAX) {
            fout<<0<<" ";
        } else {
            fout<<d[i]<<" ";
        }
    }
    return 0;
}