#include <bits/stdc++.h>

#define MAXN    50005
#define INF     2e9

#define FILENAME    std::string("dijkstra")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");

int N, M;
int dist[MAXN];
std::vector <std::pair <int, int>> ADC[MAXN];
inline void addEdge(int u, int v, int w) {
    ADC[u].push_back({v, w});
}

void dijkstra() {
    for (int i=1; i<=N; ++i) dist[i] = INF;
    std::priority_queue <std::pair <int, int>, std::vector <std::pair <int, int>>, std::greater <std::pair <int, int>>> heap;
    dist[1] = 0;
    heap.push({0, 1});
    while (!heap.empty()) {
        auto top = heap.top();
        heap.pop();
        if (top.first > dist[top.second]) continue;
        for (auto &it:ADC[top.second])
            if (dist[it.first] > it.second + top.first)
                dist[it.first] = it.second + top.first,
                heap.push({dist[it.first], it.first});
    }
}

int main()
{
    input >> N >> M;
    for (int i=1, u, v, w; i<=M; ++i)
        input >> u >> v >> w, addEdge(u, v, w);
    dijkstra();
    for (int i=2; i<=N; ++i)
        output << (dist[i] == INF ? 0 : dist[i]) << ' ';

    return 0;
}