#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int n,m,distanta[50001];

struct nod
{
    int nd;
    int val;
    struct nod *urm;
};

struct nod *vecini[50000],*q;

struct nod* extract()
{
   struct nod *u,*a,*c;
   int m=distanta[q->nd];
   c=q->urm;
   a=q;
   if(c==NULL){u=q; q=NULL; return u;}

   while(c)
   {
       if(distanta[c->nd]<m){m=distanta[c->nd]; u=a;}
       a=c; c=c->urm;

   }
  a=u; c=u->urm; u=u->urm;
   a->urm=c->urm;
   return u;
};
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);

    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)distanta[i]=50000001;
int x,y,z;
struct nod *a;
int dim=sizeof(struct nod);
for(int i=1; i<=m; i++)
{
    scanf("%d %d %d",&x,&y,&z);
    a=(struct nod*)malloc(dim);
    a->nd=y;
    a->val=z;
    a->urm=vecini[x];
    vecini[x]=a;
}
distanta[1]=0;
//bagam nodurile in coada q
for(int i=2; i<=n; i++)
{
    a=(struct nod*)malloc(dim);
    a->nd=i;
    a->urm=q;
    q=a;
}

a=vecini[1];
while(a)
{
    distanta[a->nd]=a->val;
a=a->urm;
}
while(q)
{
    struct nod *u;
    u=extract();
    a=vecini[u->nd];
    while(a)
    {
        if(distanta[u->nd]+(a->val) < distanta[a->nd])distanta[a->nd]=distanta[u->nd]+(a->val);
        a=a->urm;
    }
}

for(int i=2; i<=n; i++)printf("%d ",distanta[i]);


    return 0;
}