#include <fstream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int MAX = 5e4 + 1;
const int inf = 1e9 + 1;
int dp[MAX], n, m, x, y, c;
bool b[MAX];
struct crit{
    bool operator()( int a, int b ){
        return dp[a] > dp[b];
    }
};
priority_queue <int,vector<int>,crit> pq;
struct muchie{ int y, c;};
vector <muchie> g[MAX];

signed main(){

    cin >> n >> m;

    while(m--){
        cin >> x >> y >> c;
        g[x].push_back({y,c});
    }

    for(int i = 2 ; i <= n ; i++) dp[i] = inf;
    pq.push(1);
    while(!pq.empty()){
        x = pq.top();
        pq.pop(); b[x] = 0;
        for(auto it : g[x]){
            if(dp[it.y] > dp[x] + it.c){
                dp[it.y] = dp[x] + it.c;
                if(!b[it.y]){
                    pq.push(it.y); b[it.y] = 1;
                }
            }
        }
    }
    for(int i = 2 ; i <= n ; i++){
        if(dp[i] == inf) dp[i] = 0;
        cout << dp[i] << ' ';
    }

    return 0;
}