#include <bits/stdc++.h>

using namespace std;

int n , m;

const int inf = 2e9;

int dist[50005];

vector <pair<int,int>> adj[50005];

int main()
{
    freopen("dijkstra.in" , "r" , stdin);
    freopen("dijkstra.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= m; ++i){
        int x , y , p;
        cin >> x >> y >> p;
        adj[x].push_back({y,p});
    }
    for(int i = 1;i <= n; ++i)dist[i] = inf;
    set <pair<int,int>> d;
    d.insert({0,1});
    dist[1] = 0;
    while(!d.empty()){
        auto p = d.begin()->second;
        d.erase(d.begin());
        for(auto x : adj[p])
        {
            if(dist[x.first] > dist[p] + x.second){
                if(dist[x.first] != inf)
                    d.erase(d.find({dist[x.first],x.first}));
                dist[x.first] = dist[p] + x.second;
                d.insert({dist[x.first] , x.first});
            }
        }
    }
    for(int i = 2;i <= n; ++i)
        cout << (dist[i] == inf ? 0 : dist[i]) << " ";
}