#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;

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

int dist[NMAX+1];
bool marked[NMAX+1];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void dijkstra(int nod){
    
    dist[nod] = 0;
    pq.push({0, nod});
    
    while(!pq.empty()){
        
        int from = pq.top().second;
        int fromcost = pq.top().first;
        
        pq.pop();
        
        if(fromcost > dist[from])
            continue;
            
        marked[from] = true;
        
        for(auto per : adj[from]){
            
            int to = per.first;
            int tocost = per.second;
            
            if(dist[from] + tocost < dist[to]){
                
                dist[to] = dist[from] + tocost;
                pq.push({dist[to], to});
                
            }
            
        }
        
    }
    
}

int main()
{
    
    int n, m;
    f >> n >> m;
    
    for(int i=1; i<=m; i++){
        
        int x, y, cost;
        f >> x >> y >> cost;
        
        adj[x].push_back({y, cost});
        
    }
    
    for(int i=1; i<=n; i++)
        dist[i] = 1e9;
    
    dijkstra(1);
    
    for(int i=2; i<=n; i++)
        g << dist[i] << ' ';

    return 0;
}