#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <queue>
#include <fstream>
#include <climits>
#define NMAX 50005

using namespace std;

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

int nodes, edges;
vector <pair<int,int>> graph[NMAX];
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void input (){
    int x, y, d;

    in >> nodes >> edges;
    for (int i=1; i<=edges; ++i){
        in >> x >> y >> d;
        graph[x].push_back({y, d});
    }   
}

void findShortestPath (){
    vector <int> dist(nodes+1, INT_MAX);

    pq.push({0, 1});
    dist[1] = 0;

    while (!pq.empty()){
        int current = pq.top().second;
        pq.pop();

        for (auto idx:graph[current]){
            int node = idx.first;
            int length = idx.second;

            if (dist[current] + length < dist[node]){
                dist[node] = dist[current] + length;
                pq.push({dist[node], node});
            }
        }
    }

    for (int i=2; i<=nodes; ++i)
        out << dist[i] << ' ';
}

int main (){
    input();
    findShortestPath();

    return 0;
}