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

using namespace std;

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

int N, M;
vector<pair<int, int>> ADJ[NMAX];
int Dist[NMAX];
int VIZ[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;
        q.pop();

        if(VIZ[cur] == 1) continue;
        VIZ[cur] = 1;

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

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++)
        if(Dist[i] == INF)
            fout << "0 ";
        else
            fout << Dist[i] << ' ';
    return 0;
}