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

using namespace std;

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

const int NMAX = 50'001;
const int INF = (1LL << 31) - 1;

int N, M;
vector < pair < int, int > > G[NMAX];

vector < int > dijkstra(const int& src) {

    vector < int > dist(N + 1, INF);
    priority_queue< pair < int, int >, vector < pair < int, int > >, std::greater< pair < int, int > > > pq;

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

    while(!pq.empty()) {

        const int node = pq.top().second;
        const int cost = pq.top().first;
        pq.pop();

        if(dist[node] == cost) {

            for(pair < int, int > neighbor : G[node]) {

                if(dist[node] + neighbor.second < dist[neighbor.first]) {
                    dist[neighbor.first] = dist[node] + neighbor.second;
                    pq.push({ dist[neighbor.first], neighbor.first  });
                }
            }
        }
    }

    return dist;
}

int main() {

    f >> N >> M;

    for(int i = 1;i <= M;++i) {
        int u, v, c;
        f >> u >> v >> c;

        G[u].push_back({ v, c });
    }

    auto sol = dijkstra(1);

    for(int node = 2;node <= N;++node)
        g << sol[node] << ' ';

    return 0;
}