#include<iostream>
#include<fstream>
#include<queue>
 
using namespace std;
 
#define INF 1000000005
#define NMAX 300005
 
priority_queue< pair<int,int> > myheap; 
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));
    }
    
    myheap.push(make_pair(0, 1));
    dist[1] = 0;
    for(int i = 2; i <= n; i++) {
        dist[i] = INF;
        viz[i] = false;
    }
    
    while(!myheap.empty()) {
        pair<int, int> best = myheap.top();
        myheap.pop();
     
        int current_node = best.second;
        if(viz[current_node]) {
            continue;
        }
        viz[current_node] = true;
        
        for(auto edge : graph[current_node]) {
            int neight = edge.first;
            int cost = edge.second;

            if(dist[neight] > dist[current_node] + cost) {
                dist[neight] = dist[current_node] + cost;
                myheap.push(make_pair(-dist[neight], neight));
            }
        }
    }
    
    for(int i = 2; i <= n; i++) {
        if(dist[i] == INF) {
            g << 0;
        }
        else {
            g << dist[i];
        }
    }
    g <<"\n";
    
    return 0;
}