#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int N, M, nod, D[50003], x, y, c;

struct nod_t2 {
    int cost, y;

    bool operator<(const nod_t2 &other) const {
        return cost > other.cost;
    }
};

vector<nod_t2> G[50003], sol;
priority_queue<nod_t2> H;
bool sel[50003];

void dijkstra(int nod = 1) {
    for(int i = 1; i <= N; i++)
        D[i] = INT_MAX;
    H.push({0, nod});
    while(!H.empty()) {
        while(!H.empty() && sel[H.top().y])
            H.pop();
        if (H.empty())
            break;
        nod = H.top().y;
        sel[nod] = true;
        D[nod] = H.top().cost;
        for(auto j : G[nod])
            if(!sel[j.y])
                H.push({j.cost + D[nod], j.y});
    }
}
int main()
{
    f >> N >> M;
    for(int i = 1; i <= M; i++) {
        f >> x >> y >> c;
        G[x].push_back({c, y});
    }

    dijkstra();
    for(int i = 2; i <= N; i++)
        if(D[i] == INT_MAX) g << "0 ";
        else g << D[i] << " ";
    g << "\n";
    return 0;
}