#include <bits/stdc++.h>

using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
int cost[50005];
vector<pair<int,int> >v[50005];
bool incoada[50005];
int ncoada[50005];
queue <int> Q;
int bellman(int nod) {
    int nou,c;
    cost[nod]=0;
    Q.push(nod);
    ncoada[nod]++;
    incoada[nod]=1;
    while(!Q.empty()) {
        nod=Q.front();
        Q.pop();
        incoada[nod]=0;
        for(auto vecin:v[nod]) {
            nou = vecin.first;
            c=vecin.second;
            if(cost[nou]>c+cost[nod]) {
                cost[nou]=c+cost[nod];
                if(!incoada[nou]) {
                    if(ncoada[nou]>n)
                        return 0;
                    else {
                        ncoada[nou]++;
                        incoada[nou]=1;
                        Q.push(nou);
                    }
                }
            }
        }
    }
    return 1;
}

int main()
{
    int i,x,y,c;
    in>>n>>m;
    for(i=1;i<=n;i++)
        cost[i]=(1<<30);
    for(i=1;i<=m;i++) {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
    }
    if(bellman(1)==0) {
        out<<"Ciclu negativ!";
        return 0;
    }
    for(i=2;i<=n;i++) {
        out<<cost[i]<<" ";
    }
    return 0;
}