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

struct muchie{
    int a,b,c;
};

int N,M,c[50010]; muchie e[250010];

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

    int i,j;
    for (i=1; i<=M; i++) fin >> e[i].a >> e[i].b >> e[i].c;

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

    for (i=1; i<N; i++)
        for (j=1; j<=M; j++)
            if (c[e[j].a]+e[j].c<c[e[j].b])
                c[e[j].b]=c[e[j].a]+e[j].c;

    for (i=1; i<=M; i++)
        if (c[e[i].a]+e[i].c<c[e[i].b]){
            fout << "Ciclu negativ!\n";
            return 0;
        }

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