#include <cstdio>

using namespace std;
const int max=250000009;
struct nod{int val;int cost; nod *urm;};
nod *aux, *p[max],*q1;
int n,m,i,a,b,c,hap[100003],poz[100001],q[100003],j,t,k,nc,nrviz,min,viz[50001],dist[50001];


void inter(int a,int b)
{
         t=hap[a];
         hap[a]=hap[b];
         hap[b]=t;
         t=poz[q[a]];
         poz[q[a]]=poz[q[b]];
         poz[q[b]]=t;
         t=q[a];
         q[a]=q[b];
         q[b]=t;
};

void up(int m)
{
  if (m>1)
     if (dist[hap[m/2]]>dist[hap[m]])
       {
         inter(m/2,m);
         up(m/2);
       };
};
void down(int m)
{
   if (2*m+1<=k)
        {
           if ((dist[hap[m]]>dist[hap[2*m]])&&(dist[hap[m]]>dist[hap[2*m+1]]))
                                {
                                   if (dist[hap[2*m]]>dist[hap[2*m+1]])min=2*m+1;
                                                      else min=2*m;
                                   inter(m,min);
                                   down(min);
                                }
                          else {
                                 if (dist[hap[2*m]]<dist[hap[m]]){inter(m,2*m);down(2*m);};
                                 if (dist[hap[2*m+1]]<dist[hap[m]]){inter(m,2*m+1);down(2*m+1);};
                               };
        }
       else if ((2*m<=k)&&(dist[hap[m]]>dist[hap[2*m]])){inter(m,2*m);down(2*m);}
};

void insereaza(int x)
{
    if (poz[x]==0)
    {
    k++;
    hap[k]=x;
    poz[x]=k;
    q[k]=x;
    up(k);
    }else
       {
           j=poz[x];
           if ((j>1)&&(dist[hap[j]]<dist[hap[j/2]]))up(j);
                         else down(j);
       };
};


void sterge (int x)
{
  j=poz[x];
  if (j>0)
  {
  hap[j]=hap[k];
  poz[k]=0;
  poz[q[k]]=j;
  q[j]=q[k];
  k--;
  if ((j>1)&&(dist[hap[j]]<dist[hap[j/2]]))up(j);
                         else down(j);
  };
};

void actualdist(int s)
{
  q1=p[s];
  while (q1!=NULL)
    {

      if ((dist[s]+q1->cost)<dist[q1->val]){dist[q1->val]=dist[s]+q1->cost;insereaza(q1->val);};

      q1=q1->urm;
    };
};

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++)
     {
         scanf("%d%d%d",&a,&b,&c);
         aux=new nod; aux->val=b; aux->cost=c;aux->urm=p[a]; p[a]=aux;

     };
     for (i=1;i<=n;i++){dist[i]=max;viz[i]=0;};
     dist[1]=0;nc=1;
     nrviz=0;
     k=0;
     while (nrviz<n)
     {
         viz[nc]=1;
         nrviz++;
         sterge(nc);
         actualdist(nc);
         nc=hap[1];
     };
     for (i=2;i<=n;i++)printf("%d ",dist[i]);
        return 0;
}