#include <iostream>
#include <fstream>
#include <queue>
 
using namespace std;
 
#define INF 1000000005
#define NMAX 300005
 
priority_queue< pair<int,int> > h; 
vector< pair<int, int> > graph[NMAX];
 
int n, m, dist[NMAX];
bool viz[NMAX];
 
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
 
int main()
{
    int a, b, c;
 
    
    f >> n >> m;
    for(int i = 1; i <= m; i++) {
        f >> a >> b >> c;
        graph[a].push_back(make_pair(b, c));
    }
    
    h.push(make_pair(0, 1));
    dist[1] = 0;
    for(int i = 2; i <= n; i++) {
        dist[i] = INF;
        viz[i] = false;
    }
    
    while(!h.empty()) 
    {
        pair<int, int> best = h.top();
        h.pop();
     
        int current_node = best.second;
        if(viz[current_node]) {
            continue;
        }
        viz[current_node] = true;
        
        for(auto edge : graph[current_node]) {
            int fst = edge.first;
            int cost = edge.second;
 
            if(dist[fst] > dist[current_node] + cost) {
                dist[fst] = dist[current_node] + cost;
               h.push(make_pair(-dist[fst], fst));
            }
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF) {
            g << 0;
        }
        else {
            g << dist[i] <<' ';
        }
    }
    g <<"\n";
    
    return 0;
}