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

using namespace std;

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

const int INF = 1e9;
int N, M;
vector<pair<int, int>> *adjList;
vector<int> parrent;
vector<int> d;

void init(){
    d.resize(N+1);
    parrent.resize(N+1);
    adjList = new vector<pair<int, int>>[N+1];
    for(int u = 1; u <= N; u++)
        d[u] = INF, parrent[u] = 0;
    d[1] = 0;
}

void read(){
    fin >> N >> M;
    init();
    for(int i = 0; i < M; i++){
        int u, v, w;
        fin >> u >> v >> w;
        adjList[u].emplace_back(v, w);
    }
}

void Dijkstra() {
    read();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto p: adjList[u]) {
            int v = p.first;
            int w = p.second;
            parrent[v] = u;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                pq.push({d[v], v});
            }
        }
    }
    for(int i = 2; i <= N; i++)
        fout << d[i] << ' ';
}

int main(){
    Dijkstra();
    delete[] adjList;
    return 0;
}