#include <iostream>
#include<fstream>
#include<vector>
using namespace std;
#define MX 99999999
int d[50001],i,j,n,m,k,w,x,y,D,p[50001],h[50001],H;
long long P,Pm;
bool ok,viz[50001];
struct M
{
    int x,y,d;
}v[250001];
struct nod
{
    int x,d;
}q;
vector<nod>a[50001];
void up(int i)
{
    while(i>1&&d [ h[i] ] <d [ h[i/2] ])
    {
        swap(h[i],h[i/2]);
        p[h[i]]=i;
        p[h[i/2]]=i/2;
        i/=2;
    }
}
void down(int i)
{
    ok=0;
    while(ok<1)
    {
        if(i*2<H)
        {
            if(d[ h[i*2+1] ]>d[ h[i*2] ])
            {
                if(d[ h[i] ]>d[ h[i*2] ])
                {
                    swap(h[i],h[i*2]);
                    p[h[i]]=i;
                    p[h[i*2]]=i*2;
                    i*=2;
                }
                else ok=1;
            }
            else
            {
                if(d[ h[i] ]>d[ h[i*2+1] ])
                {
                    swap(h[i],h[i*2+1]);
                    p[h[i]]=i;
                    p[h[i*2+1]]=i*2+1;
                    i=i*2+1;
                }
                else ok=1;
            }
        }
        else
        {
            if(i*2-1<H)
            {
                if(d[ h[i] ]>d[ h[i*2] ])
                {
                    swap(h[i],h[i*2]);
                    p[h[i]]=i;
                    p[h[i*2]]=i*2;
                    ok=1;
                }
                else ok=1;
            }
            else ok=1;
        }
    }
}
void el()
{
    if(H>2)
    {
        swap(h[1],h[H]);
        p[h[1]]=1;p[h[H]]=H;
        --H;
        down(1);
    }
    else
    {
        if(H>1)
        {
            swap(h[1],h[2]);
            p[h[2]]=2;p[h[1]]=1;
            --H;
        }
        else
        {
            h[1]=0;
            --H;
        }
    }
}
void ad(int i)
{
    ++H;
    j=p[i];swap(h[H],h[j]);p[h[H]]=H;p[h[j]]=j;
    up(H);
}
int main()
{
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(i=0;i<m;++i)
    {
        f>>x>>y>>D;
        v[i].x=x;v[i].y=y;v[i].d=D;
        q.x=y;q.d=D;a[x].push_back(q);

    }
    for(i=1;i<n;++i){d[i+1]=MX;h[i+1]=i+1;p[i+1]=i;}
    H=n;h[1]=1;
    P=0;Pm=1LL*n*m;
    while(P<Pm&&h[1]>0)
    {
        x=h[1];el();
        ++P;
        k=a[x].size();
        viz[x]=0;
        for(i=0;i<k;++i)
        {
            D=a[x][i].d;y=a[x][i].x;
            if(d[y]>d[x]+D)
            {
                d[y]=D+d[x];
                if(viz[y]<1)
                {
                    viz[y]=1;
                    if(p[y]>H)
                    {
                        ad(y);
                    }
                    else up(p[y]);
                }
            }
        }
    }


    ofstream g("bellmanford.out");
    for(i=0;i<m;++i)
        {
            w=v[i].d;x=v[i].x;y=v[i].y;
            if(d[x]+w<d[y])
            {
                g<<"Ciclu negativ!";
                g.close();
                return 0;
            }
        }
    for(i=1;i<n;++i)g<<d[i+1]<<" ";
    g.close();
    return 0;
}