#include <stdio.h>
#include <vector>
using namespace std;

vector <int> a[50010];
vector <int> cost[50010];
int o,i,j,k,p,q,n,m,sum,x,t;
int heap[250010],nh[250010][2],fol[50010],dist[50010];
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",&p,&q,&k);
        a[p].push_back(q);
        cost[p].push_back(k); 
    }    
    
    p=a[1].size();k=0;
    for (i=1; i<=p; i++)
    {
        k++;
        heap[k]=cost[1][i-1];
        nh[k][0]=1;nh[k][1]=a[1][i-1];
        j=k;
        while (j>0)
        {
              if (heap[j]<heap[j>>1])
              {
                  p=heap[j];heap[j]=heap[j>>1];heap[j>>1]=p;
                  p=nh[j][0];nh[j][0]=nh[j>>1][0];nh[j>>1][0]=p;
                  p=nh[j][1];nh[j][1]=nh[j>>1][1];nh[j>>1][1]=p;
                  j>>=1;
              }
              else break;
        }
    }
    sum=0;fol[1]=1;
    while (sum<n)
    {
          if (fol[nh[1][1]]==0)
          {
              sum++;fol[nh[1][1]]=1;
              dist[nh[1][1]]=heap[1];
              t=a[nh[1][1]].size();

              for (i=1; i<=t; i++)
              {
                  k++;
                  heap[k]=heap[1]+cost[nh[1][1]][i-1];
                  nh[k][0]=nh[1][1];
                  nh[k][1]=a[nh[1][1]][i-1];

                  j=k;
                  while (j>0)
                  {         
                      if (heap[j]<heap[j/2])
                      {
                         p=heap[j];heap[j]=heap[j/2];heap[j/2]=p;
                         p=nh[j][0];nh[j][0]=nh[j/2][0];nh[j/2][0]=p;
                         p=nh[j][1];nh[j][1]=nh[j/2][1];nh[j/2][1]=p;
                         if (j>>1==1) o=j;
                         j>>=1;
                      } 
                      else break;
                  }
              }      

          }
          x=1;
          heap[1]=heap[k];nh[1][0]=nh[k][0];nh[1][1]=nh[k][1];
          k--;x=1;
          while (x*2<=k)
          {
            int p=2*x,q=2*x;
            if (2*x+1<=k) q++;
            if (heap[x]>heap[p] || heap[x]>heap[q])
            {
                if (heap[p]<=heap[q])
                {
                    t=heap[x];heap[x]=heap[p];heap[p]=t;
                    t=nh[x][0];nh[x][0]=nh[p][0];nh[p][0]=t;
                    t=nh[x][1];nh[x][1]=nh[p][1];nh[p][1]=t;
                    x=p;
                }
                else {
                        t=heap[x];heap[x]=heap[p];heap[p]=t;
                        t=nh[x][0];nh[x][0]=nh[p][0];nh[p][0]=t;
                        t=nh[x][1];nh[x][1]=nh[p][1];nh[p][1]=t;
                        x=q;
                     }
            }
            else break;
          }

    }

    for (i=2; i<=n; i++)
        printf("%d ",dist[i]);
    printf("\n");
    
    return 0;    
}