#include <iostream>
#include <fstream>
#define DMAX  50010
#define INF 1<<30

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct nod{
    int eticheta, cost;
    nod * urm;
}*v[DMAX];

int n, m;//date de intrare
bool pus[DMAX];
int heap[DMAX], lgHeap,pozitieInHeap[DMAX];
int distanta[DMAX];

void citire(){
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, c;
        in >> a >> b >> c;
        nod* deAdaugat = new nod;
        deAdaugat -> eticheta = b;
        deAdaugat -> cost = c;
        deAdaugat -> urm = v[a];
        v[a] = deAdaugat;
    }
}

void afisare(){
    for(int i = 2; i <= n; i++){
        if(distanta[i] == INF){
            out <<"0 ";
        }else{
            out << distanta[i] << ' ';
        }
    }
}


void initializare(){
    for(int i = 1; i <= n; i++){
        distanta[i] = INF;
    }
    distanta[1] = 0;
    pozitieInHeap[1] = 1;
    heap[1] = 1;
    pus[1] = true;
    lgHeap = 1;
}

int fiuStanga(int poz){
    return poz * 2;
}

int fiuDreapta(int poz){
    return  poz * 2 + 1;
}

int tata(int poz){
    return  poz/2;
}

void verificareJos(int poz){
    int fiu;
    do{
        fiu = 0;//caut fiul cu val minima
        if(fiuStanga(poz) <= lgHeap){
            fiu = fiuStanga(poz);//vad daca trebuie sa ma duc pe dreapta sau  pe stanga
            if((poz < n/2) && (distanta[heap[fiuStanga(poz)]] > distanta[heap[fiuDreapta(poz)]])){
                fiu = fiuDreapta(poz);
            }
            if(distanta[heap[fiu]] > distanta[heap[poz]]){//elementul e mai mic decat ambii fii, a.i. pe poz 1 sa fie val minima
                fiu = 0;
            }
        }
        if(fiu != 0){
            swap(heap[fiu], heap[poz]);
            swap(pozitieInHeap[heap[fiu]],pozitieInHeap[heap[poz]]);
            poz = fiu;
        }
    }while(fiu != 0);
}

void stergereHeap(int poz){
    pozitieInHeap[heap[lgHeap]] = poz;
    heap[poz] = heap[lgHeap];
    pozitieInHeap[heap[poz]] = -1;
    lgHeap--;
    verificareJos(poz);
}

void verificareDeasupra(int poz){
    while((poz > 1) &&(distanta[heap[tata(poz)]] > distanta[heap[poz]])){
        swap(pozitieInHeap[heap[tata(poz)]], pozitieInHeap[heap[poz]]);
        swap(heap[tata(poz)], heap[poz]);
        poz = tata(poz);
    }
}

void adaugareHeap(int nodul){
    heap[++lgHeap] = nodul;
    pozitieInHeap[nodul] = lgHeap;
    verificareDeasupra(pozitieInHeap[nodul]);
}

void dijkstra(){
    initializare();
    int nodMin;
    while(lgHeap >= 1){
        nodMin = heap[1];//iau valoarea minima din heap
        stergereHeap(1);
        nod * parcurg = v[nodMin];
        pus[nodMin] = true;

        while(parcurg != NULL){
            if(pus[parcurg -> eticheta] == false && (distanta[parcurg -> eticheta] == INF || distanta[nodMin] + parcurg -> cost < distanta[parcurg -> eticheta])){
                distanta[parcurg -> eticheta] = distanta[nodMin] + parcurg -> cost;
                if( pozitieInHeap[parcurg ->eticheta] != 0){
                    //pt ca i-am modificat valoarea, am micsorat-o , trb sa verific cu ce-i deasupra
                    verificareDeasupra(pozitieInHeap[parcurg -> eticheta]);
                } else{
                    adaugareHeap(parcurg -> eticheta);
                }
            }

            parcurg = parcurg -> urm;
        }
    }
}


int main() {
    citire();
    dijkstra();
    afisare();
    return 0;
}