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