#include <fstream>
#include <iostream>
#include <vector>
#include <string.h>
#define INF (1<<25)
using namespace std;
struct muchie{
    int d,c;
};
int N,M,cost[500100],heap[700100],L; vector<muchie> graf[50100]; bool viz[50100];
void ins(int nod){
    heap[++L]=nod;
    int pos=L;
    while (pos/2 && cost[heap[pos/2]]>cost[nod]){
        int aux=heap[pos/2];
        heap[pos/2]=nod;
        heap[pos]=aux;

        pos/=2;
    }
}
void del_min(){
    heap[1]=heap[L];
    L--;
    int pos=1;
    while ((cost[heap[pos]]>cost[heap[pos*2]] || cost[heap[pos]] > cost[heap[pos*2+1]]) && (pos*2 <=L)){
        if (pos*2+1>L){
            if ((cost[heap[pos]]>cost[heap[pos*2]])){
                int aux=heap[pos*2];
                heap[pos*2]=heap[pos];
                heap[pos]=aux;
                pos*=2;
            }
        }
        if (cost[heap[pos*2]]<cost[heap[pos*2+1]]){
            int aux=heap[pos*2];
            heap[pos*2]=heap[pos];
            heap[pos]=aux;

            pos*=2;
        }
        else{
            int aux=heap[pos*2+1];
            heap[pos*2+1]=heap[pos];
            heap[pos]=aux;

            pos=pos*2+1;
        }
    }
}
void calc_cost(){
    int k,nod;
    while(L){
        nod=heap[1];
        del_min();
        for (k=0; k<graf[nod].size(); k++)
            if (cost[nod]+graf[nod][k].c<cost[graf[nod][k].d]){ cost[graf[nod][k].d]=cost[nod]+graf[nod][k].c; ins(graf[nod][k].d); }
    }
}
int main()
{
    ifstream in("dijkstra.in");
    ofstream out("dijkstra.out");
    in >> N >> M;
    int i,x; muchie aux;
    for (i=0; i<M; i++){
        in >> x >> aux.d >> aux.c;
        graf[x].push_back(aux);
    }
    memset(viz,0,sizeof(viz));
    for (i=1; i<=N; i++) cost[i]=INF;
    L=1;
    cost[1]=0;
    heap[1]=1;
    calc_cost();
    for (i=2; i<=N; i++)
        if (cost[i]==INF) out << 0 << " ";
        else out << cost[i] << " ";
    return 0;
}