#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
    
    queue<int> tobevisited; //ce noduri sa vizitam
    tobevisited.push(1); //incepem de la nodul de start
    
    while(!tobevisited.empty()){//cat timp avem ce vizita
        int nod = tobevisited.front();
        tobevisited.pop();
        for(auto& vecin : arcs[nod]) {//verificam toate nodurile in care putem ajunge din nod
            if(vecin.second == inf) continue;
            if(distances[vecin.first] > distances[nod] + vecin.second) {//daca putem ajunge intr-un nod i, si ajugnem mai rapid decat stiam pana acum
                distances[vecin.first] = distances[nod] + vecin.second;//actualizam distanta
                tobevisited.push(vecin.first);//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();
}