#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;
decltype(pq.push(make_pair(0, 0))) its[maxn];

void do_dijkstra(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i = 1; i <= n; ++i) its[i] = pq.push(make_pair(dist[i], i));
    while(!pq.empty()){
        const auto cur = pq.top();
        pq.pop();
        for(const auto next : vec[cur.second]){
            if(dist[next.second] > cur.first + next.first){
                dist[next.second] = dist[cur.second] + next.first;
                pq.modify(its[next.second], 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; }