#include <bits/stdc++.h>
using namespace std;
const int nmax=5e4+5;
int n, m, sol[nmax];
vector<pair<int,int>> L[nmax];

void dijkstra (){
    priority_queue <pair<int,int>> q;
    q.push({0,1});
    while (!q.empty()){
        int node = q.top().second, dist = -q.top().first;
        q.pop();
        if (dist > sol[node]) continue;
        for (auto son : L[node]){
            if ((sol[son.first] == 0) || (sol[node] + son.second < sol[son.first])){
                sol[son.first] = son.second + sol[node];
                q.push({-sol[son.first],son.first});
            }
        }
    }
}
int main()
{
    ifstream f ("dijkstra.in");
    ofstream g ("dijkstra.out");
    f >> n >> m;
    while (m--){
        int x, y, d;
        f >> x >> y >> d;
        L[x].push_back({y,d});
    }
    sol[1] = 0;
    dijkstra();
    for (int i = 2; i <= n; ++i) g << sol[i] << " ";
    return 0;
}