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

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<int> dijkstra(int start, vector<vector<pair<int, int>>> &graph){
    int n = graph.size();
    vector<int> dist(n, INT_MAX);
    dist[start] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push(make_pair(0, start));
    while (!pq.empty()){
        auto [currentDist, node] = pq.top();
        pq.pop();
        if (currentDist <= dist[node]){
            for (auto [neighbour, weight] : graph[node]){
                int newDist = currentDist + weight;
                if (newDist < dist[neighbour]){
                    dist[neighbour] = newDist;
                    pq.push(make_pair(newDist, neighbour));
                }
            }
        }
    }
    return dist;
}

int main()
{
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 1; i <= m; i++){
        int x, y, val;
        fin >> x >> y >> val;
        graph[x].push_back(make_pair(y, val));
    }
    vector<int> dist = dijkstra(1, graph);
    for (int i = 2; i <= n; i++){
        fout << dist[i] << " ";
    }
    return 0;
}