#include <bits/stdc++.h>
#define NN 50005
#define INF 0x3f3f3f3f
using namespace std;
struct graf
{
    int nod,cost;
    graf *next;
}*a[NN];
int n,m,x,y,z,heap[NN],poz[NN],d[NN];
void add(int nod1,int nod2,int costul)
{
    graf *v=new graf;
    v->nod=nod2;
    v->cost=costul;
    v->next=a[nod1];
    a[nod1]=v;
}

void sift(int nodh)
{
int f;
while(nodh<=heap[0])
    {
    f=nodh;
    if( (nodh<<1)<=heap[0] )
        {
        f=nodh<<1;
        if(f+1<=heap[0] && d[heap[f+1]]<d[heap[f]])f++;
        }
    else return;
    if(d[heap[f]]<d[heap[nodh]])
        {
        poz[heap[nodh]]=f;
        poz[heap[f]]=nodh;

        swap(heap[nodh],heap[f]);

        nodh=f;
        }
    else return;
    }
}
void percolate(int pos)
{
    if(pos>1 && d[heap[pos]]<=d[heap[pos>>1]])
    {
        poz[heap[pos]]=pos>>1;
        poz[heap[pos>>1]]=pos;
        swap(heap[pos],heap[pos>>1]);
        percolate(pos>>1);
    }
}
void Dijkstra()
{
    heap[0]++;
    d[1]=0;
    poz[1]=1;
    heap[1]=1;
    while(heap[0])
    {
        int minim=heap[1];
        swap(heap[1],heap[heap[0]]);
        poz[heap[1]]=1;
        --heap[0];
        sift(1);
        graf *aux=a[minim];
        while(aux)
        {
            if(d[aux->nod]>d[minim]+aux->cost)
            {
                d[aux->nod]=d[minim]+aux->cost;
                if(poz[aux->nod]!=-1)
                    percolate(poz[aux->nod]);
                else
                {
                    heap[++heap[0]]=aux->nod;
                    poz[heap[heap[0]]]=heap[0];
                    percolate(heap[0]);
                }
            }
            aux=aux->next;
        }
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d\n",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1;i<=n;++i)
        d[i]=INF,poz[i]=-1;
    Dijkstra();
    for(int i=2;i<=n;++i)
        printf("%d ",d[i]==INF?0:d[i]);
}