using namespace std;
#include<fstream>
#define INFINIT 2147483647
struct nod
{
       int vf;
       int cost;
       nod*  next;
};
struct coada
{
       int info;
       coada* next;
};
int n,m,d[50005],v[50005],aparitii[50005];
nod*  G[50005];
void addarc(int,int,int);
int bellman();
int main()
{
    int i,x,y,z;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
                     fin>>x>>y>>z;
                     addarc(x,y,z);
    }
    for(i=1;i<=n;++i)
       d[i]=INFINIT;
    ofstream fout("bellmanford.out");
    if(bellman())
      fout<<"Ciclu negativ!";
    else
      for(i=2;i<=n;++i)
         fout<<d[i]<<' ';
    return 0;
}
void addarc(int i,int j,int c)
{
     nod *p=new nod;
     p->vf=j;
     p->cost=c;
     p->next=G[i];
     G[i]=p;
}
int bellman()
{
    int i;
    coada *st,*dr,*q;
    nod *p;
    st=new coada;
    dr=st;
    st->info=1;
    st->next=NULL;
    v[1]=1;
    d[1]=0;
    while(st)
    {
           i=st->info;
           v[i]=0;
           if(d[i]<INFINIT)
             for(p=G[i];p;p=p->next)
                if(d[p->vf]>d[i]+p->cost)
                {
                                         d[p->vf]=d[i]+p->cost;
                                         if(v[p->vf]==0)
                                         {
                                                        if(aparitii[p->vf]>n)
                                                          return 1;
                                                        q=new coada;
                                                        dr->next=q;
                                                        dr=dr->next;
                                                        dr->info=p->vf;
                                                        dr->next=NULL;
                                                        v[p->vf]=1;
                                                        ++aparitii[p->vf];
                                         }
                }
           q=st;
           st=st->next;
           delete q;
    }
    return 0;
}