#include<stdio.h>
#define Nmx 50001
#define INF 2000000001

int n,m,K;
int Heap[Nmx];
int Cost[Nmx],pz[Nmx];
struct nod
{
    int x,c;
    nod *urm;
};

nod *G[Nmx];

void add(int x,int y,int c)
{
    nod *aux;
    aux=new nod;
    aux->x=y;
    aux->c=c;
    aux->urm=G[x];
    G[x]=aux;
}

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        add(x,y,c);
    }
}

void schimb(int x,int y)
{
    Heap[x]^=Heap[y]^=Heap[x]^=Heap[y];
}

void sus(int k)
{
    while(k>1)
    {
        if(Cost[Heap[k/2]]>Cost[Heap[k]])
        {
            pz[Heap[k/2]]=k;
            pz[Heap[k]]=k/2;

            schimb(k,k/2);
            k=k/2;
        }
        else return ;
    }
}

void jos(int k)
{
    int t;
    while(k<=K)
    {
        if(k*2<=K)
        {
            t=k*2;
            if(k*2+1<=K)
             if(Cost[Heap[t+1]]<Cost[Heap[t]])
                ++t;
        }
        else return ;
        if(Cost[Heap[k]]>Cost[Heap[t]])
         {
            pz[Heap[k]]=t;
            pz[Heap[t]]=k;

            schimb(k,t);
            k=t;
         }
         else return ;
    }
}

void solve()
{
    for(int i=2;i<=n;++i)
       {
            Cost[i]=INF;
            pz[i]=-1;
       }
    Heap[++K]=1;
    pz[1]=1;

    while(K)
    {
        int min=Heap[1];
        schimb(1,K);
        pz[Heap[1]]=1;
        --K;

        jos(1);
        for(nod *p=G[min];p;p=p->urm)
         if(Cost[min]+p->c<Cost[p->x])
          {
                Cost[p->x]=Cost[min]+p->c;
                if(pz[p->x]!=-1)
                  sus(pz[p->x]);
                else{
                    Heap[++K]=p->x;
                    pz[p->x]=K;
                    sus(K);
                }
          }
    }
}

void print()
{
    for(int i=2;i<=n;++i)
    {
        printf("%d ",Cost[i]);
    }
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    citire();
    solve();
    print();
    return 0;
}