#include <bits/stdc++.h>
using namespace std;
 
const int INF = 1000000000;
 
int N, M;
vector<pair<int, int>> g[50005]; // first este vecinul, second este costul muchiei
int d[50005], parent[50005]; // d[i] distanta de la 1 la i
bool fixat[50005]; // initial fixat[i] = false pentru toti i
 
priority_queue<pair<int, int>> h; // first este costul drumului pana la nod, si second este nodul
 
int main() {
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back(make_pair(y, c));
    }
    
    d[1] = 0;
    for (int i = 2; i <= N; ++i)
        d[i] = INF;
    h.push(make_pair(0, 1));
    
    while (true) {
        while (!h.empty() && fixat[h.top().second])
            h.pop();
        if (h.empty())
            break;
        
        int nod = h.top().second;
        fixat[nod] = true;
        
        for (pair<int, int> p : g[nod]) {
            int vecin = p.first;
            int cost_muchie = p.second;
            if (d[vecin] > d[nod] + cost_muchie) {
                d[vecin] = d[nod] + cost_muchie;
                parent[vecin] = nod;
                h.push(make_pair(-d[vecin], vecin)); // adaugam in heap costul cu minus pentru ca pq este heap de maxim
            }
        }
    }
    
    for (int i = 2; i <= N; ++i) {
        if (d[i] == INF)
            cout << "0 ";
        else
            cout << d[i] << " ";
    }
    
    // for (int nod = 5; nod != 0; nod = parent[nod]) {
    //     cout << "\n" << nod;
    // }
    
    return 0;
}