#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int N, M;
const int inf = 0x7fffffff;
vector<pair<int,int>> arcs[50001];
vector<int> distances;

int main() {
    in >> N >> M; //citim nr noduri/arce
    distances.resize(N+1, inf); //initial consideram distantele spre toate nodurile iufinite

    for (int i = 1; i <= M; ++i) {
        int cost, a, b;
        in >> a >> b >> cost; //citim arcele
        arcs[a].emplace_back(b, cost);
    }

    distances[1] = 0; //nodul de start

    priority_queue<pair<int,int>, vector<pair<int, int>>, greater<pair<int,int>>> tobevisited; //ce noduri sa vizitam
    tobevisited.push(make_pair(0,1)); //incepem de la nodul de start si distanta la care l-am adaugat

    while(!tobevisited.empty()){//cat timp avem ce vizita
        pair<int,int> nod = tobevisited.top();
        tobevisited.pop();
        if(distances[nod.second] < nod.first) continue; //daca la momentul cand am cerut sa revizuim distantele traseul era mai lung decat acum, trecem de aceasta vizita
        for(auto& vecin : arcs[nod.second]) {//verificam toate nodurile in care putem ajunge din nod
            int destinatie = vecin.first, cost = vecin.second;
            if(distances[destinatie] > distances[nod.second] + cost) {//daca putem ajunge intr-un nod i, si ajugnem mai rapid decat stiam pana acum
                distances[destinatie] = distances[nod.second] + cost;//actualizam distanta
                tobevisited.push(make_pair(distances[destinatie], destinatie));//si revizitam nodul sa verificam daca se scurteaza si alte distante
            }
        }
    }

    for (int i = 2; i <= N; ++i) {
        if (distances[i] == inf) {
            distances[i] = 0;
        }
        out << distances[i] << ' ';
    }
    out << '\n';

    in.close();
    out.close();
}