#include <bits/stdc++.h>
#define NMAX 50001
#define INF 2e9

using namespace std;

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

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

void Dijkstra() {
    priority_queue<pair<int, int>> q;
    q.push({0, 1});
    for(int i = 1; i <= N; i++) Dist[i] = INF;
    Dist[1] = 0;
    while (!q.empty()) {
        int cur = q.top().second;
        int d = -q.top().first;
        q.pop();

        for (auto next : ADJ[cur]) {
            int new_dist = d + next.second;
            if(Dist[next.first] > new_dist) {
                Dist[next.first] = new_dist;
                q.push({-new_dist, next.first});
            }
        }
    }
}

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        ADJ[a].push_back({b, c});
    }
    Dijkstra();
    for(int i = 2; i <= N; i++)
        fout << Dist[i] << ' ';
    return 0;
}