#include <fstream>
#define maxn 50010
#define maxm 250010
#define inf 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,H_size=0,H[maxn+5],dist[maxn+5];
bool viz[maxn+5];
struct nod
{
    int info,cost;
    nod *urm;
}*v[maxn+5],*c,*e[maxn+5]={NULL};
inline int tata(int k)
{
    return k>>1;
}
inline int fius(int k)
{
    return k<<1;
}
inline int fiud(int k)
{
    return k<<1+1;
}
void up_heap(int k)
{
    int key=k,aux;
    while(k>1 && key<=H_size && dist[H[key]]<dist[H[tata(key)]])
    {
        aux=H[key];
        H[key]=H[tata(key)];
        H[tata(key)]=aux;
        key=tata(key);
    }
}
void down_heap(int k)
{
    int son,key=k,aux;
    do
    {
        son=0;
        if(fius(key)>1 && fius(key)<=H_size)
            son=fius(key);
        if(fiud(key)>1 && fiud(key)<=H_size && dist[H[fiud(key)]]<dist[H[fius(key)]])
            son=fiud(key);
        if(dist[H[key]]<dist[H[son]])
        {
            aux=H[key];
            H[key]=H[son];
            H[son]=aux;
            key=son;
        }
        else
        son=0;
    }while(son && key>1 && key<H_size);
}
void heapify()
{
    for(int i=H_size/2;i>0;i--)
        down_heap(i);
}
void baga(int x)
{
   H[++H_size]=x;
   up_heap(x);
}
void sterge(int k)
{
    H[k]=H[H_size];
    H_size--;
    if(k>1 && dist[H[k]]<dist[H[tata(k)]])
        up_heap(k);
    else
        down_heap(k);
}
bool check_negative()
{
    for(int i=1;i<=n;i++)
    {
        c=v[i];
        while(c->urm)
        {
            c=c->urm;
            if(dist[i]+c->cost<dist[c->info])
                return true;
        }
    }
    return false;
}
int main()
{
    int x,y,z,pas=0;
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->urm=0;
        v[i]->cost=0;
        dist[i]=inf;
    }
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        if(!e[x])
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->cost=z;
            v[x]->urm=c;
            e[x]=c;
        }
        else
        {
            c=new nod;
            c->info=y;
            c->urm=0;
            c->cost=z;
            e[x]->urm=c;
            e[x]=c;
        }
    }
    dist[1]=0;
    dist[0]=-inf;
    baga(1);
    while(H_size && pas<=1LL*n*m)
    {
        pas++;
        x=H[1];
        sterge(1);
        c=v[x];
        viz[x]=0;
        while(c->urm)
        {
            c=c->urm;
            if(dist[x]+c->cost<dist[c->info])
            {
                dist[c->info]=dist[x]+c->cost;
                if(!viz[c->info])
                {
                    baga(c->info);
                    viz[c->info]=1;
                }
            }
        }
        heapify();
    }
    if(check_negative())
    {
        fout<<"Ciclu negativ!\n";
        return 0;
    }
    else
    for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
    return 0;
}