#include <cstdio>

using namespace std;
FILE *in=fopen ("dijkstra.in","r");
FILE *out=fopen ("dijkstra.out","w");
const int M=250001,N=50001,INF=999999;
int n,m,lst[N],vf[M],urm[M],q[2*M],cost[M],d[N],v[N],h[N],poz[N],nh;
void adauga (int x,int y,int z)
{
    vf[++m]=y;
    cost[m]=z;
    urm[m]=lst[x];
    lst[x]=m;
}
void schimb (int p1,int p2)
{
    int aux=h[p1];
    h[p1]=h[p2];
    h[p2]=aux;
    poz[h[p1]]=p1;
    poz[h[p2]]=p2;
}
void urca(int p)
{
    while (p>1 && v[h[p]]< v[h[p/2]])
    {
        schimb (p,p/2);
        p/=2;
    }
}
void coboara (int p)
{
    int fs=2*p,fd=2*p+1,bun=p;
    if (fs<=nh && v[h[fs]]<v[h[bun]]) bun=fs;
    if (fd<=nh && v[h[fd]]<v[h[bun]]) bun=fd;
    if (bun!=p)
    {
        schimb (bun,p);
        coboara(bun);
    }
}
void stergeH (int p)
{
    schimb (p,nh--);
    urca(p);
    coboara(p);
}
void adaugaH (int x)
{
    h[++nh]=x;
    poz[x]=nh;
    urca(nh);
}
void afisare ()
{
    for (int i=2;i<=n;i++)
        fprintf(out,"%d ",d[i]);
}
void dijkstra (int x0)
{
    int x,y,c,pozitie;
    for (int i=1; i<=n; i++)
    {
        d[i]=INF;
        poz[i]=0;
    }
    nh=0;
    h[++nh]=x0;
    d[x0]=0;
    while (nh!=0)
    {
        x=h[1];
        stergeH(1);
        pozitie=lst[x];
        while (pozitie!=0)
        {
            y=vf[pozitie];
            c=cost[pozitie];
            if (d[x]+c<d[y])
            {
                d[y]=d[x]+c;
                if (poz[y]==0) adaugaH(y);
                else urca(poz[y]);
            }
            pozitie=urm[pozitie];
        }
    }
    afisare();
}
void citire ()
{
    int a;
    fscanf (in,"%d%d",&n,&a);
    for (int i=1;i<=a;i++)
    {
        int x,y,z;
        fscanf (in,"%d%d%d",&x,&y,&z);
        adauga(x,y,z);
    }
    dijkstra(1);
}
int main()
{
    citire();
    return 0;
}