#include <bits/stdc++.h>
using namespace std;

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

const int INF = 0x3F3F3F3F;
const int MAXN = 50005;
typedef pair<int,int> PII;

vector<PII> g[MAXN];
int dp[MAXN], n;
bool viz[MAXN];

priority_queue<PII, vector<PII>, greater<PII>> heap;

void Dijkstra(int nodeStart) {
    for(int i = 1; i <= n; i++)
        dp[i] = INF;

    dp[1] = 0;
    heap.emplace(0, 1);

    while(heap.size()) {
        int node = heap.top().second;
        heap.pop();

        if(viz[node] == false) {
            viz[node] = true;
            for(auto nxt : g[node])
                if(dp[nxt.first] > nxt.second + dp[node]) {
                    dp[nxt.first] = nxt.second + dp[node];
                    heap.emplace(dp[nxt.first], nxt.first);
                }
        }
    }
}

int main() {
    int m, x, y, cost;
    fin >> n >> m;

    for(int i = 1; i <= m; i++) {
        fin >> x >> y >> cost;
        g[x].emplace_back(y, cost);
    }

    Dijkstra(1);

    for(int i = 2; i <= n; i++)
        fout << (dp[i] == INF ? 0 : dp[i]) << " ";

    return 0;
}