#include <bits/stdc++.h>
#define MAX 100100
#define INF 999999999

using namespace std;

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

int n, m;
vector < pair <int, int> > G[MAX];
int D[MAX];

void dijkstra(){
    priority_queue < pair <int, int>, vector < pair <int, int> >, greater < pair < int, int > > > pq;
    pq.push({0, 1});
    while (!pq.empty()){
        int nod = pq.top().second;
        int val = pq.top().first;
        pq.pop();
        if (D[nod] != val) continue;
        for (int i = 0; i < G[nod].size(); i++){
            int nodnou = G[nod][i].first;
            int valnou = G[nod][i].second;
            if (D[nodnou] > valnou + val){
                D[nodnou] = valnou + val;
                pq.push({D[nodnou], nodnou});
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    f >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y, z;
        f >> x >> y >> z;
        G[x].push_back({y, z});
    }
    D[1] = 0;
    for (int i = 2; i <= n; i++){
        D[i] = INF;
    }
    dijkstra();
    for (int i = 2; i <= n; i++){
        if (D[i] == INF){
            g << "0 ";
        } else {
            g << D[i] << ' ';
        }
    }
    return 0;
}