#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#include <bitset>
#define NMAX 50020
#define oo (1<<30)
using namespace std;

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

int n, m, distanta[NMAX]; //vectorul distanta are semnificatia: distanta[i] = de la nodul sursa la nodul i avem costul d[i]

struct compare{

bool operator()(int x, int y){ //functie ce stabileste prioritatea in coada

return distanta[x]>distanta[y];

}

};

vector<pair<int, int>> graf[NMAX];

priority_queue<int, vector <int>, compare> coada; //coada de prioritate cu trei parametrii ( tipul de data, modul in care se acceseaza elementele si o functie de prioritate
                                                  //functia stabileste dupa ce criteriu sunt aranjate elementele in coada. Primul element e cel cu prioritatea cea mai mica

bitset<NMAX> inCoada;

void citire(){

f>>n>>m;

for(int i=1; i<=m; i++){

    int x, y, c;
    f>>x>>y>>c;
    graf[x].push_back(make_pair(y, c));

}

}

void afisare(){

for(int i=2; i<=n; i++)
    if(distanta[i]!=oo) g<<distanta[i]<<" ";
    else g<<"0 ";

}

void dijkstra(int source){

for(int i=1; i<=n; i++)
    distanta[i]=oo;     //setam distantele de la sursa la toate nodurile cu infinit

distanta[source]=0;
coada.push(source);
inCoada[source]=1;

while(!coada.empty()){

    int nodCurent = coada.top();  // se ia nodul cu cost minim de la sursa la el (asta face coada de prioritate)

    coada.pop();
    inCoada[nodCurent]=0;

    for(auto nod : graf[nodCurent]){  //pentru fiecare vecin al unui nod din coada vedem daca putem sa stabilim traseu intre sursa si vecin prin nodul curent

        int vecin = nod.first; //cine e vecin
        int cost = nod.second; //costul de la nodul curent la vecin

        if(distanta[vecin] > distanta[nodCurent] + cost){
            distanta[vecin]=distanta[nodCurent] + cost;
            if(!inCoada[vecin]){

                inCoada[vecin]=1;
                coada.push(vecin);

            }
        }

    }

}

}

int main()
{

citire();
dijkstra(1);
afisare();

    return 0;
}