#include <bits/stdc++.h>
#define INF 99999999
#define MAX 51000

using namespace std;

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

vector < pair <int, int> > G[MAX];
int n, m;
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 node = pq.top().second;
        int value = pq.top().first;
        pq.pop();

        if (D[node] != value) continue;
        for (int i = 0; i < G[node].size(); i++){
            if (value + G[node][i].second < D[G[node][i].first]){
                D[G[node][i].first] = value + G[node][i].second;
                pq.push({D[G[node][i].first], G[node][i].first});
            }
        }
    }
}

void dostuff(){
    f >> n >> m;
    for (int i = 1; i <= m; i++){
        int x, y, d;
        f >> x >> y >> d;
        G[x].push_back({y, d});
    }
}

void domorestuff(){
    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] << ' ';
        }
    }
}

int main()
{
    dostuff();
    domorestuff();
    return 0;
}