#include<cstdio>
#include<fstream>
#define INFINIT 2000000000
#define H h
#define heap h
#define cost c
#define MAX 50005
using namespace std;
struct nod{
    int info, c;
    nod *next;
};
inline int f(int k){
    return k/2;}
inline int r_son(int k){
    return k*2+1;}
inline int l_son(int k){
    return k*2;}
nod *G[MAX];
int d[MAX],nh,n,t[MAX],h[MAX],poz[MAX];

void addarc(int x,int y,int c)
{
    nod *p=new nod;
    p->cost=c;
    p->info=y;
    p->next=G[x];
    G[x]=p;
}

void promoveaza(int k)
{
    while(k>1 && d[h[f(k)]]>d[h[k]])
    {
        swap(h[f(k)],h[k]);
        swap(poz[h[f(k)]],poz[h[k]]);
        k=f(k);
    }
}

void cerne(int k)
{
    int son;
    do
    {
        son=0;
        if(l_son(k)<=nh)
        {
            son=l_son(k);
            if(r_son(k)<=nh && d[h[r_son(k)]]<d[h[son]])
                son=r_son(k);
            if(d[h[k]]<=d[h[son]])
                son=0;
        }
        if(son)
        {
            swap(h[son],h[k]);
            swap(poz[h[son]],poz[h[k]]);
            k=son;
        }
    }while(son);
}

void init(int s)
{
    int i,ps;
    for(i=0;i<=n;i++)
        d[i]=INFINIT,t[i]=-1,h[i]=i,poz[i]=i;
    nh=n,ps=poz[s];
    d[s]=0,t[s]=0;
    swap(h[ps],h[nh]);
    swap(poz[h[ps]],poz[h[nh]]);
    nh--;
    cerne(ps);
    for(nod *p=G[s]; p ; p=p->next)
        if(d[s]+p->c<d[p->info])
        {
            d[p->info]=d[s]+p->c;
            t[p->info]=s;
            promoveaza(poz[p->info]);
        }
}

void dijkstra(int s)
{
    init(s);
    for(int qq=1;qq<n;qq++)
    {
        int k=h[1];
        if(d[k]==INFINIT)
            break;
        h[1]=h[nh--];
        poz[h[1]]=1;
        for(nod *p=G[k];p;p=p->next)
            if(d[k]+p->c<d[p->info])
            {
                d[p->info]=d[k]+p->c;
                t[p->info]=k;
                promoveaza(poz[p->info]);
            }
    }
}

int main()
{
    int i,m;
    ifstream fin("dijkstra.in");
    freopen("dijkstra.out","w",stdout);
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        addarc(x,y,c);
    }
    dijkstra(1);
    for(i=2;i<=n;i++)
        printf("%d ", d[i]);
    return 0;
}