#include<cstdio>
#include<algorithm>

const int NMAX=50001,INF=1<<30;

std::vector<std::pair<int,int> > vecini[NMAX];

bool fol[NMAX];

struct muchie{int x,y,cost;};

muchie muchii[NMAX];

int dist[NMAX];

int heap[NMAX],poz[NMAX],marime_heap;

int tata(int nod)
{
 return nod/2;
}

int fiu_st(int nod)
{
 return 2*nod;
}

int fiu_dr(int nod)
{
 return 2*nod+1;
}

void Swap(int x,int y)
{
 std::swap(heap[x],heap[y]);
 std::swap(poz[heap[x]],poz[heap[y]]);
}

void Up(int nod)
{
 while(nod>1 && dist[heap[tata(nod)]]>dist[heap[nod]])
       {
        Swap(nod,tata(nod));
        nod=tata(nod);
       }
}

void Down(int nod)
{
 while(nod<marime_heap)
       {
        int best=nod;
        if(fiu_st(nod)<=marime_heap && dist[heap[fiu_st(nod)]]<dist[heap[best]])
           best=fiu_st(nod);
        if(fiu_dr(nod)<=marime_heap && dist[heap[fiu_dr(nod)]]<dist[heap[best]])
           best=fiu_dr(nod);
        if(best==nod)
           return;
        Swap(best,nod);
        nod=best;
       }
}

void Add(int val)
{
 heap[++marime_heap]=val;
 poz[val]=marime_heap;
 fol[val]=true;
 Up(marime_heap);
}

void Remove_min()
{
 fol[heap[1]]=false;
 Swap(1,marime_heap);
 marime_heap--;
 Down(1);
}

int Get_min()
{
 return heap[1];
}

void Init(int n)
{
 for(int i=1;i<=n;i++)
     {
      heap[i]=i;
      dist[i]=INF;
      poz[i]=i;
      //fol[i]=true;
     }
 dist[1]=0;
 marime_heap=n;
}

bool BellmanFord(int n,int m)
{
 int pas=0;
 while(marime_heap!=0 && pas<=n*m&& dist[Get_min()]!=INF)
       {
        int sq=Get_min();
        Remove_min();
        pas++;
        for(std::vector<std::pair<int,int> >::iterator i=vecini[sq].begin();i!=vecini[sq].end();i++)
            {
             int a=i->first,b=i->second;
             if(dist[i->first]>dist[sq]+i->second)
                {
                 dist[i->first]=dist[sq]+i->second;
                 if(!fol[i->first])
                    {
                     Add(i->first);
                    }
                /* else
                    {
                     Up(poz[i->first]);
                    }*/
                }
            }
        //Remove_min();
       }
 for(int i=1;i<=m;i++)
     {
      if(dist[muchii[i].y]>dist[muchii[i].x]+muchii[i].cost)
         return true;
     }
 return false;
}

int main()
{
 FILE *in=fopen("bellmanford.in","r");
 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      fscanf(in,"%d %d %d ",&muchii[i].x,&muchii[i].y,&muchii[i].cost);
      vecini[muchii[i].x].push_back(std::make_pair(muchii[i].y,muchii[i].cost));
     }
 fclose(in);
 FILE *out=fopen("bellmanford.out","w");
 Init(n);
 if(BellmanFord(n,m))
    fprintf(out,"Ciclu negativ!\n");
 else
    {
     for(int i=2;i<=n;i++)
         fprintf(out,"%d ",dist[i]);
    }
 fclose(out);
 return 0;
}