#include<cstdio>
#include<vector>

#define NMAX 50015
#define oo 1<<30

using namespace std;

int N,M,Nheap;

int H[NMAX],Hp[NMAX];     // H[]  = heap pe distante
int D[NMAX];       // D[i] = dist (1,i)
int A[NMAX];       // A[i] = nodul anterior lui i
bool used[NMAX];

struct nod{
    int vecin,cost;
};

vector < nod > G[NMAX];

inline int father(int nod){
    return nod>>1;
}

inline int left_son(int nod){
    return nod<<1;
}

inline int right_son(int nod){
    return (nod<<1)+1;
}

void swap(int &i, int &j)
{
    int aux;

    aux=Hp[i];
    Hp[i]=Hp[j];
    Hp[j]=aux;

    aux=i;
    i=j;
    j=aux;

}

void percolate(int nod){

    while(nod>1 && D[H[nod]]<D[H[father(nod)]])
    {
        int p=father(nod);
        swap(H[nod],H[p]);
        nod=father(nod);
    }
}

void sift(int nod){

    int son;
    do{
        son=0;

        if(left_son(nod)<=Nheap)
        {
            son=left_son(nod);
            if(right_son(nod)<=Nheap && D[H[son]]>D[H[right_son(nod)]])
                son=right_son(nod);
            if(D[H[son]]>D[H[nod]])
                son=0;
        }
        if(son)
            swap(H[son],H[nod]);
        nod=son;
    }while(son);
}

void Read(){

    freopen("dijkstra.in","r",stdin);
    scanf("%d%d",&N,&M);
    int i,nod1,nod2,cost;
    for(i=1;i<=M;i++)
    {
        scanf("%d%d%d",&nod1,&nod2,&cost);
        G[nod1].push_back({nod2,cost});
    }
}

void Initialize_Distances(){

    for(int i=2;i<=N;i++)
        H[i]=Hp[i]=i,D[i]=oo;
}

void Create_Heap(){

    for(int i=1;i<=N;i++)
    {
        H[i]=D[i];
        percolate(i);
    }
}

void Dijkstra(){

    Nheap=N;
    int current_nod;
    H[1]=Hp[1]=1;

    while(Nheap)
    {
        current_nod=H[1];
        used[current_nod]=true;
        //swap(Hp[H[1]],Hp[H[Nheap]]);
        swap(H[1],H[Nheap--]);
        sift(1);

        for(unsigned i=0;i<G[current_nod].size();++i)
        {
            if(used[G[current_nod][i].vecin]==true)
                continue;
            if(D[G[current_nod][i].vecin]>D[current_nod]+G[current_nod][i].cost)
            {
                D[G[current_nod][i].vecin]=D[current_nod]+G[current_nod][i].cost;
                A[G[current_nod][i].vecin]=current_nod;
               /* swap(Hp[H[G[current_nod][i].vecin]],Hp[H[Nheap]]);
                swap(H[Hp[G[current_nod][i].vecin]],H[Nheap]);*/
                if(Hp[G[current_nod][i].vecin]>1 && H[Hp[G[current_nod][i].vecin]]<H[father(Hp[G[current_nod][i].vecin])])
                    percolate(Hp[G[current_nod][i].vecin]);
                else
                    sift(Hp[G[current_nod][i].vecin]);
            }
        }

    }
}

void rec(int i){

    if(A[i])
        rec(A[i]);
    printf("%d ",i);
}

void Print(){

    freopen("dijkstra.out","w",stdout);
    for(int i=2;i<=N;i++)
    {
      /*  printf("%d = %d : ",i,D[i]);
        rec(i);
        printf("\n");*/
        printf("%d ",D[i]);
    }
}

int main(){

    Read();
    Initialize_Distances();
    Dijkstra();
    Print();
   // Create_Heap();
    return 0;
}