using namespace std;
#include<fstream>
#define INFINIT 2147483647
struct nod
{
       int vf;
       int cost;
       nod*  next;
};
int n,m,d[50005],v[50005],aparitii[50005];
nod*  G[50005];
void addarc(short,short,short);
int bellman();
int main()
{
    nod *p;
    int i,x,y,z,ciclu;
    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(short i,short j,short c)
{
     nod *p=new nod;
     p->vf=j;
     p->cost=c;
     p->next=G[i];
     G[i]=p;
}
int bellman()
{
    int st,dr,i,coada[50005];
    nod *p;
    st=dr=1;
    coada[st]=1;
    v[1]=1;
    d[1]=0;
    while(st<=dr)
    {
           i=coada[st++];
           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;
                                                        coada[++dr]=p->vf;
                                                        v[p->vf]=1;
                                                        ++aparitii[p->vf];
                                         }
                }
    }
    return 0;
}