#include <stdio.h>
using namespace std;
FILE *f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");
const int INF=250000001;
int n,m,i,x,y,c,dist[50001],h[50001],poz[50001];
struct nod {int y; int c; nod* next;};
nod *G[50001],*it;
int add(int x, int y,int c)
{
    nod *nou=new nod;
    nou->y=y;
    nou->c=c;
    nou->next=G[x];
    G[x]=nou;
    return 0;
}
int uph(int p)
{
    int aux;
    while(p/2!=0)
    {
        if (dist[h[p/2]]>dist[h[p]])
        {
            aux=h[p/2];
            h[p/2]=h[p];
            h[p]=aux;
            poz[h[p]]=p;
            poz[h[p/2]]=p/2;
            p=p/2;
        }
        else p=0;
    }
    return 0;
}
int downh(int p)
{
    int min,aux;
    while(2*p<=h[0])
    {
      min=2*p;
      if (2*p+1<=h[0] && dist[h[2*p+1]]<dist[h[min]]) min=2*p+1;
      if (dist[h[min]]<dist[h[p]])
      {
          aux=h[min];
          h[min]=h[p];
          h[p]=aux;
          poz[h[p]]=p;
          poz[h[min]]=min;
          p=min;
      }
      else p=h[0]+1;
    }
    return 0;
}
int main(void)
{
    fscanf(f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
    dist[1]=0;
    for(i=2;i<=n;i++) dist[i]=INF;
    h[++h[0]]=1;
    poz[1]=1;
    while(h[0])
    {
        x=h[1];
        poz[x]=0;
        if (h[0]!=1) { h[1]=h[h[0]]; poz[h[1]]=1; downh(1);}
        h[0]--;
        it=G[x];
        while(it!=NULL)
        {
            y=it->y;
            c=it->c;
            if (dist[y]>dist[x]+c)
            {
                dist[y]=dist[x]+c;
                if (!poz[y])
                {
                    h[++h[0]]=y;
                    poz[y]=h[0];
                    uph(h[0]);
                }
                else uph(poz[y]);
            }
            it=it->next;
        }
    }
    for(i=2;i<=n;i++)
    {
      if(dist[i]==INF) dist[i]=0;
      fprintf(g,"%d ",dist[i]);
    }
    fprintf(g,"\n");
    return 0;
}