#include<stdio.h>
#include<stdlib.h>
#define Max  10001
#define Nmax 50001
int  d[Nmax],n;
bool s[Nmax];
struct nod
     {
      int info,c;
      nod *urm;
     };
typedef nod *Lista;
Lista L[Nmax];
inline void Insert(int x,int y,int cost)
     {
       Lista q=new nod;
       q->info=y; q->c=cost;
       q->urm=L[x];
       L[x]=q;
      }
void Dijkstra(int);
int main()
  {int m,i,x,y,cost;
   //froepen("dijkstra.in","rt",stdin);
   //freopen("dijkstra.out","wt",stdout);
   scanf("%d %d",&n,&m);
   for(i=1;i<=n;++i)
       for(int j=1;j<=m;++j) Insert(i,j,Max);
   for(i=1;i<=m;++i) scanf("%d %d %d",&x,&y,&cost),Insert(x,y,cost);
   Dijkstra(1);
   for(i=2;i<=n;++i) printf("%d ",d[i]);
   system("PAUSE");
   return 0;
  }
void Dijkstra(int x)
   {s[x]=1;
    int  i,min,j,y;
    Lista p,q;
    for(i=1,p=L[x];p&&i<=n;p=p->urm,i++)  d[i]=p->c;
    for(i=1;i<n;++i)
       {
        for(p=L[x],j=1,min=Max;j<=n;++j,p=p->urm)
           if(s[j]==0&&d[j]<min) {min=d[j]; y=j; q=p;}
        s[y]=1;
        for(j=1;j<=n;++j)
           if(s[j]==0&&d[j]>q->c+d[y]) d[j]=q->c+d[y];
       }
    }