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

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

struct arc {
    int cost, nod;
};
std::vector<arc> nodes[50000];
int n, m;

bool operator<(arc a, arc b) { return a.cost > b.cost; }

std::priority_queue<arc> q;

int drum_minim[50000];
bool visited[50000];
int main() {
    in >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b, cost;
        in >> a >> b >> cost;
        a--, b--;
        nodes[a].push_back({cost, b});
    }

    q.push({0, 0});
    while (!q.empty()) {
        auto top = q.top();
        q.pop();
        if (visited[top.nod]) continue;
        visited[top.nod] = 1;
        drum_minim[top.nod] = top.cost;
        for (auto &el : nodes[top.nod]) {
            if (!visited[el.nod]) q.push({top.cost + el.cost, el.nod});
        }
    }

    for (int i = 1; i < n; i++) out << drum_minim[i] << ' ';
}