#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];//coada+distante(sol)
struct muchie{
    int x;
    int y;
    int val;
}v[250001];
bool viz[50001];
void bellmanford(int k){
    for(int i=1;i<=n;++i)
        d[i]=inf;
    d[k]=0;
    while(inc<=sf){
        for(int i=1;i<=m && v[i].x<=c[inc];++i)//pana cand parcurgem toate muchiile sau trecem de cele cu aceeasi val de la inceputul cozii
            if(v[i].x==c[inc] && v[i].val+d[v[i].x]<d[v[i].y] && d[v[i].x]!=inf){//daca am ajuns la muchiile de la pozitia initiala a cozii si drumul care trece prin nodul intermediar e mai scurt si neinfinit
                d[v[i].y]=v[i].val+d[v[i].x];
                if(viz[v[i].y]==false){
                     ++sf;
                    c[sf]=v[i].y;//adaugam elem in coada
                    viz[v[i].y]=true;
                }
            }
        ++inc;
    }
    //verificam prezenta unui ciclu negativ
    bool pas=false;
    for(int i=1;i<=m && v[i].x<=1;++i)//pana cand parcurgem toate muchiile sau trecem de cele cu aceeasi val de la inceputul cozii
            if(v[i].x==1 && v[i].val+d[v[i].x]<d[v[i].y] && d[v[i].x]!=inf){//daca am ajuns la muchiile de la pozitia initiala a cozii si drumul care trece prin nodul intermediar e mai scurt si neinfinit
                d[v[i].y]=v[i].val+d[v[i].x];
                if(viz[v[i].y]==false){
                     ++sf;
                    c[sf]=v[i].y;//adaugam elem in coada
                    viz[v[i].y]=true;
                }
                pas=true;
            }
    if(pas==false)
        for(int i=2;i<=n;++i)
            out<<d[i]<<" ";
    else
        out<<"Ciclu negativ!";
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
        in>>v[i].x>>v[i].y>>v[i].val;
    c[inc]=1;
    bellmanford(1);
    return 0;
}