#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int INFINITY = 1 << 30;

ifstream input("dijkstra.in");
ofstream output("dijkstra.out");

vector<pair<int, int>> adj[50001];
int dist[50001] = {};
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> p_q;

int main()
{
    int N, M;
    input >> N >> M;
    for(int i = 0; i < M; i++){
        int x, y, z;
        input >> x >> y >> z;
        adj[x].push_back({y, z});
    }
    p_q.push({0, 1});
    for(int i = 2; i <= N; i++){
        dist[i] = INFINITY;
    }
    for(int i = 0; i < adj[1].size(); i++){
        p_q.push({adj[1][i].second, adj[1][i].first});
    }
    while(!p_q.empty()){
        pair<int, int> curr_dist;
        curr_dist = p_q.top();
        p_q.pop();
        if(curr_dist.first == dist[curr_dist.second]){
            for(int i = 0; i < adj[curr_dist.second].size(); i++){
                if(dist[adj[curr_dist.second][i].first] > dist[curr_dist.second] + adj[curr_dist.second][i].second){
                    dist[adj[curr_dist.second][i].first] = dist[curr_dist.second] + adj[curr_dist.second][i].second;
                }
                p_q.push({dist[adj[curr_dist.second][i].first], adj[curr_dist.second][i].first});
            }
        }

    }
    for(int i = 2; i <= N; i++){
        output << dist[i] << " ";
    }
    return 0;
}