#include <fstream>
#include <vector>
#define NMAX 50009
using namespace std;

FILE * fin =fopen ("bellmanford.in", "r");
FILE * fout =fopen("bellmanford.out", "w");

struct graf
{
    int v, c;
};

int n, m;
int aparitii[NMAX], coada[100*NMAX], cmin[NMAX];
bool uz[NMAX];
vector <graf>L[NMAX];

void citire ();
void bellmanford ();
void afisare();

int main()
{
    citire();
    bellmanford();
    return 0;
}

void citire ()
{
    int a, b, i;
    graf aux;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        fscanf(fin, "%d %d %d\n", &a, &b, &aux.c);
        aux.v=b;
        L[a].push_back(aux);
        //aux.v=a;
        //L[b].push_back(aux);
    }
}

void bellmanford ()
{
    int i, prim, ultim, vf;
    for(i=1; i<=n; ++i)
        cmin[i]=1000000000;
    prim=ultim=0;
    coada[++ultim]=1;
    uz[1]=1;
    aparitii[1]=1;
    cmin[1]=0;
    while(prim<=ultim)
    {
        vf=coada[++prim];
        uz[vf]=0;
        for(i=0; i<L[vf].size(); ++i)
            if(cmin[L[vf][i].v]>cmin[vf]+L[vf][i].c)
            {

                cmin[L[vf][i].v]=cmin[vf]+L[vf][i].c;
                ++aparitii[L[vf][i].v];
                if(! uz[L[vf][i].v])
                {
                    coada[++ultim]=L[vf][i].v;
                    uz[L[vf][i].v]=1;
                }
                if(aparitii[L[vf][i].v]==(n-1) )
                {
                    fprintf(fout, "Ciclu negativ!\n");
                    fclose(fout);
                    return;
                }
            }
    }
    afisare();
}

void afisare()
{
    int i;
    for(i=2; i<=n; ++i)
        fprintf(fout, "%d ", cmin[i]);
    fclose(fout);
}