#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[2*N_MAX],poz[2*N_MAX],D[2*N_MAX],T[2*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)
{
   // g<<"HD "<<r<<'\n';
    int st=0,dr=0,i=0;
    if(2*r+1<=k)
    {
        st=2*r+1;
        if(2*r+2<=k) dr=2*r+2;
        else dr=st+1;
    }
    if(st==dr&&st==0) return;
    if(st>dr) i=2*r+1;
    else
    {
        if(D[H[st]]<D[H[dr]]) i=2*r+1;
        else i=2*r+2;
    }
   // g<<D[H[r]]<<" + "<<D[H[i]]<<'\n';
    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()
{
    int i;
    swap1(0,nh-1);
    poz[H[nh-1]]=0;
    nh--;
   // for(i=0;i<nh;++i) g<<"("<<H[i]<<" "<<D[H[i]]<<") ";
   // g<<'\n';
    HeapDown(0,nh-1);
   // for(i=0;i<nh;++i) g<<"("<<H[i]<<" "<<D[H[i]]<<") ";
   // g<<'\n';
    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();
       // g<<nod<<'\n';
        p=G[nod];
        for(p=G[nod];p;p=p->leg)
            if(D[p->nod]>D[nod]+p->c)
                {
                 // g<<nod<<" * "<<p->nod<<'\n';
                  D[p->nod]=D[nod]+p->c;
                  T[p->nod]=nod;
                  HeapUp(poz[p->nod]);
                }
      /* for(i=0;i<nh;++i) g<<"("<<H[i]<<" "<<D[H[i]]<<") ";
       g<<'\n';*/
    }
}
int main()
{
    lista *p;
    citire();
    /*for(i=1;i<=n;++i)
    {
        g<<i<<'\n';
        for(p=G[i];p;p=p->leg) g<<p->nod<<" "<<p->c<<'\n';
        g<<'\n';
    }*/
    Dy(1);
    for(i=2;i<=n;++i)
    { if(D[i]!=50000001) g<<D[i]<<" ";
      else g<<"0 ";
    }
    return 0;
}