//#include<algorithm>
//using namespace std;
#include<stdio.h>

#define DIM 50001
#define INF 1000001

struct djk{
    int d,f;};

struct graf{
    int nod,cost;
    graf *urm;};

struct heap{
    int poz,val;};

int n,m,cnt;
djk a[DIM];
graf *lst[DIM];
heap h[DIM];

inline int fath(int nod){

    return nod/2;}

inline int lson(int nod){

    return 2*nod;}

inline int rson(int nod){

    return 2*nod+1;}

void add(int a,int b,int c){
    graf *p=new graf;

    p->nod=b;
    p->cost=c;
    p->urm=lst[a];
    lst[a]=p;}

void swap(int a,int b){
    heap aux;

    aux=h[a];
    h[a]=h[b];
    h[b]=aux;}

void uph(int k){
    int poz,val;

    for(poz=h[k].poz,val=h[k].val; k>1&&h[k].val>h[fath(k)].val; k=fath(k)){
        h[k]=h[fath(k)];
    h[k].val=val;
    h[k].poz=poz;}}

void downh(int k){
    int son;

    do{
        son=0;
		if(lson(k)<=cnt){
			son=lson(k);
			if(rson(k)<=cnt&&h[rson(k)].val>h[lson(k)].val)
                son=rson(k);
            if(h[son].val<=h[k].val)
                son=0;}
        if(son){
            swap(k,son);
            k=son;}}
    while(son);}


void insert(int poz,int val){

    h[++cnt].poz=poz;
    h[cnt].val=val;
    uph(cnt);}

void cut(int k){

	h[k]=h[cnt--];
	if(k>1&&h[k].val>h[fath(k)].val)
        uph(k);
    else
        downh(k);}

void init(){
    int i;

    for(i=2; i<=n; ++i)
        a[i].d=INF;}

void dijkstra(){
    int i,j;
    graf *p;

    h[cnt=1].val=0;
    h[cnt].poz=1;
    for(i=1; i<=n; ++i){
        a[h[1].poz].f=1;
        for(p=lst[h[1].poz]; p; p=p->urm)
            if(h[1].val+p->cost<a[p->nod].d){
                a[p->nod].d=a[h[1].poz].d+p->cost;
                if(!a[p->nod].f)
                    insert(p->nod,a[p->nod].d);}
        cut(1);}}

void solve(){
    int i,a,b,c;

    scanf("%d%d",&n,&m);
    for(i=0; i<m; ++i){
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);}
    init();
    dijkstra();}

void print(){
    int i;

    for(i=2; i<=n; ++i)
        printf("%d ",a[i].d!=INF?a[i].d:0);}

int main(){

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

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