#include <iostream>
#include <vector>
#include <functional>
#include <queue>
#include <limits.h>
#define MAX_N 50005
#define lol long long

using namespace std;

vector<pair<int, long long> > edges[MAX_N];
long long dp[MAX_N];
priority_queue<pair<lol, int>, vector<pair<lol, int> >, greater<pair<lol, int> > > pq;
int main()
{
    FILE * fin = fopen("dijkstra.in", "r");
    FILE * fout = fopen("dijkstra.out", "w");
    int n, m;
    fscanf(fin, "%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        long long a, b, c;
        fscanf(fin, "%lld %lld %lld", &a, &b, &c);
        a--;
        b--;
        edges[a].push_back({b, c});
    }
    for (int i = 1; i < n; i++)
        dp[i] = LLONG_MAX;
    dp[0] = 0;
    pq.push({0, 0});
    while (!pq.empty()) {
        auto tp = pq.top();
        pq.pop();
        if (tp.first != dp[tp.second])
            continue;
        for (auto j: edges[tp.second]) {
            lol neww = j.second + dp[tp.second];
            if (dp[j.first] > neww) {
                dp[j.first] = neww;
                pq.push({dp[j.first], j.first});
            }
        }
    }
    for (int i = 1; i < n; i++)
        fprintf(fout, "%lld ", dp[i]);
    fprintf(fout, "\r\n");
}