#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;

constexpr int maxn = 5e4 + 100;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int, int>> vec[maxn] = {};
int n, m, dist[maxn] = {};
__gnu_pbds::priority_queue<pair<int, int>, greater<pair<int, int>>>
    pq;

void do_dijkstra(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while(!pq.empty()){
        int cur = pq.top().second, cur_dist = pq.top().first;
        pq.pop();
        if(dist[cur] != cur_dist) continue;
        for(const auto next : vec[cur]){
            if(cur_dist + next.first < dist[next.second]){
                dist[next.second] = cur_dist + next.first;
                pq.push(make_pair(dist[next.second], next.second)); } } } }

int main(){
    f >> n >> m;
    for(int i = 0, x, y, z; i < m; ++i){
        f >> x >> y >> z;
        vec[x].emplace_back(z, y); }
    do_dijkstra();
    transform(dist+2, dist+n+1, ostream_iterator<int>(g, " "),
        [](const int x){ return x > 1e9 ? 0 : x; });
    return 0; }