#include<stdio.h>

#define nmax 50001
#define inf  30000000

int n,m,sol[nmax],lh[nmax];

struct nod
{
    int drum,cost;
    nod *urm;
} *l[nmax];

struct heap
{
    int v,ind;
} h[nmax];

void add(nod *&,int,int);
void dijkstra();
void sift(int,int);
void percolate(int);
void swap(int,int);

int main()
{
    int a,b,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(l[a],b,c);
        }
    dijkstra();
    for(int i=2;i<=n;++i)
        printf("%d ",sol[i]);
    printf("\n");
    return 0;
}


void add(nod *&inc,int info1,int info2)
{
    nod *p=new nod;
    p->drum=info1;
    p->cost=info2;
    p->urm=inc;
    inc=p;
}

void sift(int k,int n2)
{
    int fiu=1;
    while (fiu)
        {
            fiu=0;
            if (2*k <= n2)
                {
                fiu= 2*k;
                if (2*k+1 <= n2 && h[fiu].v > h[2*k+1].v)
                    fiu= 2*k+1;
                if (h[fiu].v >= h[k].v)
                    fiu=0;
                }
            
            if (fiu)
                {
                    swap(k,fiu);
		    k=fiu;
                }    
        }
}

void percolate(int k)
{
    while (k/2 > 0 && h[k].v < h[k/2].v)   
        {
            swap(k,k/2);
            k=k/2;
        }
}

void dijkstra()
{
    for(int i=1;i<=n;++i)    
	{
	h[i].v=inf;
	h[i].ind=i;
        lh[i]=i;
	sol[i]=inf;
	}
    sol[1]=0;
    h[1].v=0;

    for(int nlate=n;nlate;)
    {
        int pmin=h[1].ind;
        swap(nlate,1);
        --nlate;
        sift(1,nlate);
        
        
        
        nod *t=l[pmin];
    
        while (t)
            {
                if (sol[t->drum] > t->cost + sol[pmin])
                    {
                    sol[t->drum] = t->cost + sol[pmin];
                    if (lh[t->drum] <= nlate)
                        {
                        h[ lh[t->drum] ].v= t->cost + sol[pmin];
                        percolate( lh[t->drum] );
                        }
                    }
                
                t=t->urm;
            }
    }
}


void swap(int a,int b)
{
    heap c=h[a];
    h[a]=h[b];
    h[b]=c;
    
    lh[h[a].ind]=a;
    lh[h[b].ind]=b;
    
}