#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <climits>
const int INF = INT_MAX;
const int N = 50000;
struct arc {
    int to, weight;
};
std::vector<arc> arce[N + 1];
int d[N + 1];
int main()
{
    std::ifstream fin("dijkstra.in");
    std::ofstream fout("dijkstra.out");
    int n, m;
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int to, from, weight;
        fin >> from >> to >> weight;
        from--; to--;
        arce[from].push_back({ to,weight });
    }
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[0] = 0;
    using con = std::pair<int, int>;
    //coada de prioritate care tine perechi de inturi si le pastreaza strict crescator.
    std::priority_queue <con, std::vector<con>, std::greater<con>> q;
    q.push({ 0,0 });
    while (!(q.empty())) {
        if (q.top().first != d[q.top().second]) {
            q.pop();
            continue;
        }
        int nod = q.top().second;
        q.pop();
        for (const auto& greu : arce[nod]) {
            if (d[nod] + greu.weight < d[greu.to]){
                d[greu.to] = d[nod] + greu.weight;
                q.push({ d[greu.to],greu.to });
            }
        }
    }
    for (int i = 1; i < n; i++) {
        if (d[i] == INF) {
            fout << 0 << ' ';
        }
        else
            fout << d[i] << ' ';
    }
    return 0;
}