#include <bits/stdc++.h>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


int n,m,a,b,cost,d[50005];
vector <pair<int,int>> v[50005];
priority_queue <pair<int,int>> pq;


void Dijkstra(){
    while (!pq.empty()){
        int cost = pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        for (int i = 0; i < v[nod].size(); i++){
            if (cost + v[nod][i].second < d[v[nod][i].first]){
                 d[v[nod][i].first] = cost + v[nod][i].second;
                 pq.push({d[v[nod][i].first], v[nod][i].first});
            }
        }
    }

}


int main()
{
fin>>n>>m;
for (int i = 1; i <= m; i++){
    fin>>a>>b>>cost;
    v[a].push_back({b, cost});
}
for (int i = 1; i <= n; i++){
    d[i] = 999999999;
}
d[1] = 0;
pq.push({0, 1});
Dijkstra();
for (int i = 2; i <= n; i++){
    if (d[i] == 999999999)
        d[i] = 0;
    fout << d[i] << " ";
}


return 0;
}