#include <bits/stdc++.h>

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

const int inf = 1e9;
int n,m;
int dmin[50005],viz[50005],incoada[50005];
vector<pair<int,int>>L[50005];
queue<int>q;

bool bellmanford(int start){
    for(int i = 1; i <= n; i++){
        viz[i] = 0;
        incoada[i] = 0;
        dmin[i] = inf;
    }

    dmin[start] = 0;
    q.push(start);
    incoada[start] = 1;

    while(!q.empty()){
        int nod = q.front();
        q.pop();
        incoada[nod] = 0;

        viz[nod]++;
        if(viz[nod] >= n) return false;

        int nr = L[nod].size();
        for(int i = 0; i < nr; i++){
            int vecin= L[nod][i].second,
                cost = L[nod][i].first;

            if(dmin[vecin] > dmin[nod] + cost){
                dmin[vecin] = dmin[nod] + cost;
                if(!incoada[vecin])
                    q.push(vecin);
            }
        }
    }
    return true;
}


int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int a,b,c;
        in >> a >> b >> c;
        L[a].push_back({c,b});
    }
    if(bellmanford(1)){
        for(int i = 2; i <= n; i++)
            out << dmin[i] << " ";
    }
    else out << "Ciclu negativ!";
    return 0;
}