#include <fstream>
#include <stdint.h>
#define nmax 50001
#define mmax 250001
using namespace std;
fstream f1("bellmanford.in", ios::in);
fstream f2("bellmanford.out", ios::out);
int32_t n, m, aux[nmax], cap[nmax], d[nmax], pred[nmax];
int16_t ok=1;
const int32_t inf= 250000000;
struct muchii
{
    int32_t x, y, c;
}muc[mmax];
struct list_ad
{
    int32_t vec, c;
} v[mmax];
void citire()
{
    int32_t i, x, y, c;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        aux[x]++;
        muc[i].x=x;
        muc[i].y=y;
        muc[i].c=c;
    }
    cap[1]=1;
    for(i=2; i<=n+1; i++)
        {
            cap[i]=cap[i-1]+ aux[i-1];
            aux[i-1]=cap[i-1];
        }
    for(i=1; i<=m; i++)
    {
        x=muc[i].x;
        y=muc[i].y;
        v[aux[x]].vec=y;
        v[aux[x]].c=muc[i].c;
        aux[x]++;
    }
}
void bellam_ford()
{
    int32_t i, j, k;
    for(i=1; i<=n; i++)///incerci sa optimizezi de n ori toate muchiile de la j la k
        for(j=1; j<=n; j++)
            for(k=cap[j]; k<cap[j+1]; k++)
                if((j!= v[k].vec)&&(d[v[k].vec]> d[j] +v[k].c))//j, v[k].vec, v[k].c
                {
                    d[v[k].vec]= d[j] +v[k].c;
                    pred[v[k].vec]=j;
                }
}
void init()
{
    int32_t i;
    for(i=2; i<=n; i++)
    {
        pred[i]=1;
        d[i]=inf;
    }
    for(i=cap[1]; i<cap[2]; i++)
        d[v[i].vec]= v[i].c;
}
void verif_c_neg()
{
    int32_t i, j;
    for(i=1; (i<=n)&&ok; i++)
        for(j=cap[i]; (j<cap[i+1])&&ok; j++)
            if((i!= v[j].vec)&&(d[v[j].vec]> d[i]+ v[j].c))
    {
        f2<<"Ciclu negativ!";
        ok=0;
        break;
    }
}
void afisare()
{
    int32_t i;
    for(i=2; i<=n; i++)
        f2<<d[i]<<" ";
}
int main()
{
    citire();
    init();
    bellam_ford();
    verif_c_neg();
    if(ok)
        afisare();
    return 0;
}