#include <queue>
#include <vector>
#include <fstream>

#define DMAX 50010

using std::vector;
using std::priority_queue;

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

struct Arc {
    int node;
    int cost;
};

int n, m;
vector<Arc> ad[DMAX];

int dp[DMAX];
priority_queue<int> pq;

int main() {
    int a, b, c;

    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        ad[a].push_back({b, c});
    }

    pq.push(1);
    while (!pq.empty()) {
        int node = pq.top();
        pq.pop();

        for (Arc arc : ad[node])
            if (!dp[arc.node] || dp[node] + arc.cost < dp[arc.node]) {
                dp[arc.node] = dp[node] + arc.cost;
                pq.push(arc.node);
            }
    }

    for (int i = 2; i <= n; i++)
        fout << dp[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}