#include<stdio.h>
#include<vector>
using namespace std;

FILE *f = fopen("dijkstra.in","r");
FILE *g = fopen("dijkstra.out","w");

typedef vector<pair<int,int> >::iterator it;

#define MaxN 50100
#define MaxAINT 200100
#define mij ((li+ls)>>1)
#define fs (poz<<1)
#define fd ((poz<<1)+1)
#define INF (1<<29)

int N,M;
vector<pair<int,int> > A[MaxN];
int D[MaxN];
int AINT[MaxAINT],POZAINT[MaxAINT];

void citire(void)
{
    int a,b,c;
    fscanf(f,"%d %d\n",&N,&M);
    for(int i=1;i<=M;i++)
    {
        fscanf(f,"%d %d %d\n",&a,&b,&c);
        A[a].push_back(make_pair(b,c));
    }
}

void initializare(void)
{
    for(int i=1;i<MaxAINT;i++)
        AINT[i] = INF;
}

inline int min(int a,int b)
{
    return a < b ? a : b;
}

inline void insertAINT(int li,int ls,int poz,int val,int pozVal,int how)
{
    if(li == ls)
    {
        if(how == 1)
            AINT[poz] = val,POZAINT[poz] = li;
        else
        {
            if(AINT[poz] == INF+1)
                return ;
            AINT[poz] = min(AINT[poz],val),POZAINT[poz] = li;
        }
        return ;
    }

    if(li <= pozVal && pozVal <= mij)
        insertAINT(li,mij,fs,val,pozVal,how);
    else
        insertAINT(mij+1,ls,fd,val,pozVal,how);

    if(AINT[fs] > AINT[fd])
        AINT[poz] = AINT[fd],POZAINT[poz] = POZAINT[fd];
    else
        AINT[poz] = AINT[fs],POZAINT[poz] = POZAINT[fs];
}

inline void adauga(int cost,int a)
{
    for(it i=A[a].begin();i<A[a].end();i++)
    {
//        printf("... %d %d, AINT[1] = %d, %d\n",cost+i->second,i->first,AINT[1]
//            ,POZAINT[1]);
        insertAINT(1,N,1,cost+i->second,i->first,2);
    }
}

inline void dijkstra(void)
{
    initializare();

    adauga(0,1);
    insertAINT(1,N,1,INF+1,1,1);

    for(int i=2;i<=N;i++)
    {
    //    printf("%d %d\n",AINT[1],POZAINT[1]);
        D[POZAINT[1]] = AINT[1];
        int poz = POZAINT[1];
        adauga(AINT[1],poz);
        insertAINT(1,N,1,INF+1,poz,1);
    }
}

int main()
{
    citire();
    dijkstra();

    for(int i=2;i<=N;i++)
        fprintf(g,"%d ",D[i]);
}