#include<fstream>
#include<string.h>
#define N_MAX 50009
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct lista{int nod,c;
             lista *leg;
             } *G[N_MAX];
int H[N_MAX],poz[N_MAX],D[N_MAX],T[N_MAX],nh,n,m,i;
void swap1(int i,int j)
{
    int aux;
    aux=H[i];
    H[i]=H[j];
    H[j]=aux;
    poz[H[i]]=i;
    poz[H[j]]=j;
}
void HeapDown(int r,int k)
{
    int st=0,dr=0,i;
    if(2*r+1<=k)
    {
        st=H[2*r+1];
        if(2*r+2<=k) dr=H[2*r+2];
        else dr=st+1;
    }
    if(st==dr&&st==0) return;
    if(st>dr) i=2*r+1;
    else i=2*r+2;
    if(D[H[r]]>D[H[i]])
    {
        swap1(r,i);
        HeapDown(i,k);
    }
}
void HeapUp(int k)
{
    int t;
    if(k<=0) return;
    t=(k-1)/2;
    if(D[H[k]]<D[H[t]])
    {
        swap1(k,t);
        HeapUp(t);
    }
}
int scoate()
{
    swap1(0,nh-1);
    poz[H[nh-1]]=0;
    nh--;
    HeapDown(0,nh-1);
    return H[nh];
}
void BuildH(int k)
{
    int i;
    for(i=0;i<k;++i) HeapUp(i);
}
void adaug(int i,int j,int c)
{
    lista *p;
    p=new lista;
    p->nod=j; p->c=c;
    p->leg=G[i];
    G[i]=p;
}
void citire()
{
    f>>n>>m;
    int i,j,c;
    while(m--)
    {
        f>>i>>j>>c;
        adaug(i,j,c);
    }
}
void Dy(int s)
{
    int i,nod;
    lista *p;
    memset(T,0,sizeof T);
    for(i=1;i<=n;++i) D[i]=50000001;
    D[s]=0;
    for(i=0;i<=n;++i)
    {
        H[i]=i+1;
        poz[i+1]=i;
    }
    BuildH(n); nh=n;
    while(nh>0)
    {
        nod=scoate();
        p=G[nod];
        for(p=G[nod];p;p=p->leg)
            if(D[p->nod]>D[nod]+p->c)
                {
                  D[p->nod]=D[nod]+p->c;
                  T[p->nod]=nod;
                  HeapUp(poz[p->nod]);
                }
    }
}
int main()
{
    lista *p;
    citire();
    Dy(1);
    for(i=2;i<=n;++i) g<<D[i]<<" ";
    g<<'\n';
    return 0;
}