#include <bits/stdc++.h>

using namespace std;

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

const int INF = 2000000000;

int N, M;
vector <int> Ad[50005];
vector <int> Cost[50005];

int dist[50005];
priority_queue<pair<int, int>> Q;

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; ++i) {
        int a, b, cost;

        fin >> a >> b >> cost;

        Ad[a].push_back(b);
        Cost[a].push_back(cost);
    }

    // initializam distantele

    for(int i = 1; i <= N; ++i)
        dist[i] = INF;

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

    while(Q.size() > 0) {
        int u = Q.top().second;
        Q.pop();

        int w;
        for(int i = 0; i < Ad[u].size(); ++i) {
            w = Ad[u][i];

            if(dist[u] + Cost[u][i] < dist[w]) {
                dist[w] = dist[u] + Cost[u][i];
                Q.push({dist[w], w});
            }
        }
    }

    for(int i = 2; i <= N; i++)
        fout << dist[i] << ' ';

    return 0;
}