#include <iostream>
#include <fstream>
#define inf 65536
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m;
int c[3000000],inc=1,sf=1,d[50001],viz[50001];//coada+distante(sol)+vizitat
struct nod{
    int vecin;
    int val;
    struct nod *urm;
}*l[50001],*actual;
bool bellmanford(int k){
    c[inc]=k;//pun in coada elementul sursa
    for(int i=1;i<=n;++i)
        d[i]=inf;//initializez distantele cu +inf
    d[k]=0;
    while(inc<=sf){//cat timp exista elemente in coada
        actual=l[c[inc]];
        while(actual!=NULL){
            //daca drumul prin elem din inceputul cozii este mai scurt + am vizitat de mai putin de n-1 ori
            if(actual->val+d[c[inc]]<d[actual->vecin] /*&& viz[actual->vecin]!=n-1*/){
                //atribuim noul minim
                d[actual->vecin]=actual->val+d[c[inc]];
                //adaugam in coada
                ++sf;
                c[sf]=actual->vecin;
                //crestem nr de vizite
                ++viz[actual->vecin];
                //daca am vizitat de n-1 ori rezulta ciclu infinit
                if(viz[actual->vecin]==n-1)
                    return false;
            }
            actual=actual->urm;
        }
        ++inc;
    }
    return true;//nu exista ciclu
}
int main()
{
    in>>n>>m;
    int x,y,valt;
    for(int i=1;i<=m;++i){
        in>>x>>y>>valt;
        actual=new nod;
        actual->vecin=y;
        actual->urm=l[x];
        actual->val=valt;
        l[x]=actual;
    }
    bool ok=bellmanford(1);
    if(ok==false)
        out<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            out<<d[i]<<" ";
    return 0;
}