#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;
}
int ind_min(int nod)
{
    if(nod<<1 +1 <=heap[0])
        return ((d[heap[nod<<1]]<d[heap[nod<<1 +1]])?(nod<<1):(2*nod+1));
    return nod<<1;
}
void sift(int nod)
{
    if(2*nod<=heap[0])
    {
        int ind=ind_min(nod);
        if(d[heap[nod]]>d[heap[ind]])
        {
            poz[heap[nod]]=ind;
            poz[heap[ind]]=nod;
            swap(heap[nod],heap[ind]);
            sift(ind);
        }
    }
}
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]);
}