// LENT
#include <fstream>
#define fisier "dijkstra"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
const int N = 50001, C = 20000, INF = N*C;
int D[N];
#include <utility>
#define c first
#define f second
using Arc = std::pair<int, int>;
#include <vector>
std::vector<Arc> L[N];
#include <queue>
#include <algorithm>
int main()
{
    int n, m;
    in >> n >> m;
    while (m--)
    {
        int a, b, c;
        in >> a >> b >> c;
        L[a].push_back({c, b});
    }
    std::priority_queue<Arc> Q;
    std::fill(D+2, D+n+1, INF);
    for (Q.push({0, 1}); Q.size();)
    {
        int t = Q.top().f;
        Q.pop();
        for (Arc arc: L[t])
            if (D[t] + arc.c < D[arc.f])
            {
                D[arc.f] = D[t] + arc.c;
                Q.push({-D[arc.f], arc.f});
            }
    }
    for (int i = 2; i <= n; i++)
        out << D[i] << ' ';
}