#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

struct muchie{
    int b,c;
};

int N,M,K,c[50010],q[100000],v[50010]; vector<muchie> graf[50010];

int main(){
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin >> N >> M;

    int i,j,l,x,b,cost,t; muchie aux;
    for (i=1; i<=M; i++){
        fin >> x >> aux.b >> aux.c;
        graf[x].push_back(aux);
    }

    for (i=1; i<=N; i++) c[i]=(1<<30);
    c[1]=0;

    q[++K]=1;
    for (i=1; i<N; i++){
        l=0;
        for (j=1; j<=K; j++)
            for (t=0; t<graf[q[j]].size(); t++){
                b=graf[q[j]][t].b;
                cost=graf[q[j]][t].c;
                if (c[q[j]]+cost<c[b]){
                    c[b]=c[q[j]]+cost;
                    if (v[b]!=i) { q[++l]=b; v[b]=i; }
                }
            }
        K=l;
    }

    for (i=1; i<N; i++)
        for (j=0; j<graf[i].size(); j++)
            if (c[i]+graf[i][j].c<c[graf[i][j].b]){
                fout << "Ciclu negativ!\n";
                return 0;
            }

    for (i=2; i<=N; i++) fout << c[i] << " ";
    return 0;
}