#include <fstream>
#include <algorithm>
#define NMAX 999999999
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Nod{int inf,c; Nod* leg;};
typedef Nod* nod;

nod a[50002],inc,sf;
int c[50002],numar[50002],n,m,viz[50002];

void add(nod &q, int x, int z)
{
    nod p=new Nod;
    p->inf=x;
    p->c=z;
    p->leg=q;
    q=p;
}

void add2(int x)
{
    viz[x]=1;
    numar[x]++;
    nod p=new Nod;
    p->inf=x;
    p->leg=NULL;
    sf->leg=p;
    sf=p;
}

void sterg(nod &q)
{
    viz[q->inf]=0;
    nod p=q->leg;
    delete q;
    q=p;

}

int main()
{
    int i,x,y,z;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>z;
        add(a[x],y,z);
        c[i]=NMAX;
    }
    c[1]=0;
    viz[1]=1;
    numar[1]++;
    nod p=new Nod;
    p->inf=1;
    p->leg=NULL;
    inc=p;
    sf=p;

    while (inc)
    {
        nod p;
        x=inc->inf;
        for(p=a[x];p;p=p->leg)
            if(c[p->inf]>c[x]+p->c)
            {
                c[p->inf]=c[x]+p->c;
                if(!viz[p->inf])
                {
                    add2(p->inf);
                    if(numar[p->inf]>n) {fout<<"Ciclu negativ!"; return 0;}
                }
            }
        sterg(inc);
    }
    for(i=2; i<=n; i++) fout<<c[i]<<" ";
    return 0;
}