#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define MAX_N 50001
#define inf 1061109567
int n,m,H[MAX_N],T[MAX_N],D[MAX_N],pos[MAX_N],nh;
char U[MAX_N];
struct lista
{
    int nod,c;
    lista* urm;
}*G[MAX_N];
void adauga_nod(lista*&p, int n, int C)
{
    lista* c = new lista;
    c->nod = n;
    c->c = C;
    c->urm=p;
    p=c;
}
void citeste()
{
    ifstream f("dijkstra.in");
    f>>n>>m;
    int x,y,c;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y>>c;
        adauga_nod(G[x],y,c);
        adauga_nod(G[y],x,c);
    }
    f.close();
}
void schimba(int i, int j)
{
    swap(H[i],H[j]);
    pos[H[i]]=i;
    pos[H[j]]=j;
}
void HeapDW(int x)
{
    x*=2;
    while(x<=nh)
    {
        if(x<nh && D[H[x]]>D[H[x+1]]) x++;
        if(D[H[x/2]]>D[H[x]]) schimba(x/2,x);
        else x=nh+1;
        x*=2;
    }
}
void HeapUP(int x)
{
    while(x/2)
    {
        if(D[H[x/2]]>D[H[x]]) schimba(x/2,x);
        else break;
        x/=2;
    }
}
void BuildHeap()
{
    for(int i=n/2;i>0;i--)
        HeapDW(i);
}
int Heap_out()
{
    schimba(1,nh);
    pos[H[nh]]=0;nh--;
    HeapDW(1);
    return H[nh+1];
}
void dijkstra(int s)
{
    int nod;
    lista* p;
    memset(U,0,sizeof(U));
    memset(T,0,sizeof(T));
    memset(D,inf,sizeof(D));
    for(int i=1;i<=n;i++)
        H[i]=i,pos[i]=i;
    D[s]=0;nh=n;
    BuildHeap();
    while(nh)
    {
        nod = Heap_out();
        for(p=G[nod];p;p=p->urm)
            if(D[p->nod]>D[nod]+p->c)
            {
                D[p->nod] = D[nod]+p->c;
                T[p->nod]=nod;
                HeapUP(pos[p->nod]);
            }
    }
}
int main()
{
    citeste();
    dijkstra(1);
    ofstream g("dijkstra.out");
    for(int i=2;i<=n;i++)
        if(D[i]==inf) g<<"0 ";
        else g<<D[i]<<" ";
    g.close();
    return 0;
}