#include <iostream>
#include <fstream>
#define inf 2147483647
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,a,b,c;
struct nod{
    int vecin;
    int cost;
    struct nod *urm;
}*l[50001],*q;
int viz[50001];
int h[50001],nr;
int d[50001],mn;

void add_h(int nr){
    int poz=nr;
    while(poz>1 && h[poz/2]>h[poz]){
        int t=h[poz/2];
        h[poz/2]=h[poz];
        h[poz]=t;

        t=viz[poz/2];
        viz[poz/2]=viz[poz];
        viz[poz]=t;

        poz/=2;
    }
}
void del_vf(int &nr){
    h[1]=h[nr];
    int t=viz[1];
    viz[1]=viz[nr];
    viz[nr]=t;
    --nr;
    int poz=1;
    while(2*poz<=nr){
        int fiu=2*poz;
        if(fiu+1<=nr && h[fiu+1]<h[fiu])
            ++fiu;
        if(h[fiu]<h[poz]){
            int t=h[poz];
            h[poz]=h[fiu];
            h[fiu]=t;

            t=viz[poz];
            viz[poz]=viz[fiu];
            viz[fiu]=t;

            poz=fiu;
        }
        else poz=nr+1;
    }
}
void dijkstra(int p){
    for(int i=2;i<=n;++i)
        d[i]=inf;
    viz[p]=inf;
    q=l[p];
    while(q!=NULL){
        d[q->vecin]=q->cost;

        ++nr;
        viz[q->vecin]=nr;
        h[nr]=q->vecin;
        add_h(nr);

        q=q->urm;
    }
    while(nr>0){
        mn=h[p];
        del_vf(nr);
        q=l[mn];
        while(q!=NULL){
            if(d[q->vecin]>d[mn]+q->cost){
                d[q->vecin]=d[mn]+q->cost;

                if(viz[q->vecin]==0){
                    ++nr;
                    viz[q->vecin]=nr;
                    h[nr]=q->vecin;
                    add_h(nr);
                }
                else
                    add_h(viz[q->vecin]);
            }
            q=q->urm;
        }
    }
}
int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i){
        in>>a>>b>>c;
        q=new nod;
        q->vecin=b;
        q->cost=c;
        q->urm=l[a];
        l[a]=q;
    }
    dijkstra(1);
    for(int i=2;i<=n;++i)
        out<<d[i]<<" ";
    return 0;
}