#include <bits/stdc++.h>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int NMAX = 5e4;
const int MMAX = 1e5;

const int VMAX = 1e9;

vector<pair<int, int>> adj[NMAX+1];
priority_queue<pair<int, int>> q;
int rez[NMAX+1];

void dijkstra(int from, int val){
    rez[from] = val;
    q.push({-val, from});
    
    while(!q.empty()){
        
        int vf = q.top().second;
        int dist = -q.top().first;
        q.pop();
        
        //cout << vf << ' ' << dist << endl;
        
        if( rez[vf] != dist )
            continue;
        
        for(auto nod : adj[vf]){
            
            int cost = nod.second;
            int to = nod.first;
            
            if(dist + cost < rez[to]){
                q.push({-cost-dist, to});
                rez[to] = cost + dist; 
            }
            
            
                
        }
    }
}

int main()
{
    int n, m;
    f >> n >> m;
    
    fill(rez+1, rez+1+n, VMAX);
    
    for(int i=1; i<=m; i++){
        
        int from, to, val;
        f >> from >> to >> val;
        //cout << from << ' ' << to << ' ' << val << endl;
        adj[from].push_back({to, val});
        
    }
    
    dijkstra(1, 0);
    for(int i=2; i<=n; i++)
        if(rez[i] == VMAX)
            g << 0 << ' ';
        else g << rez[i] << ' ';

    return 0;
}