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

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

int n, m;
int d[50005], viz[50005];
std::vector<std::pair<int, int>> L[50005];
std::priority_queue<std::pair<int, int>> q;

void Dijkstra() {
    int x, cost;
    d[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        x = q.top().second; cost = -q.top().first;
        q.pop();
        if (viz[x] == 0) {
            viz[x] = 1;
            for (auto w : L[x]) {
                if (d[w.first] > d[x] + w.second) {
                    d[w.first] = d[x] + w.second;
                    q.push(std::make_pair(-d[w.first], w.first));
                }
            }
        }
    }
}

int main() {
    int x, y, cost;
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> cost;
        L[x].push_back(std::make_pair(y, cost));
    }


    for (int i = 1; i <= n; i++) {
        d[i] = 2e9;
    }

    Dijkstra();

    for (int i = 2; i <= n; i++) {
        fout << d[i] << " ";
    }
}