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

struct arc {
    int to, weight;
};

std::vector<arc> arce[50000];
int dist[50000];

const int INF = 1 << 30;

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 from, to, weight;
        fin >> from >> to >> weight;
        from--; to--;
        arce[from].push_back({to, weight});
    }

    for (int i = 0; i < n; i++) {
        dist[i] = INF;
    }

    dist[0] = 0;
    // cost, nod
    using pii = std::pair<int, int>;
    std::priority_queue<pii, std::vector<pii>, std::greater<pii>> q;
    q.push({0, 0});

    while (!q.empty()) {
        int nod = q.top().second;
        q.pop();
        for (const auto& succ : arce[nod]) {
            if (dist[nod] + succ.weight < dist[succ.to]) {
                dist[succ.to] = dist[nod] + succ.weight;
                q.push({dist[succ.to], succ.to});
            }
        }
    }

    for (int i = 1; i < n; i++) {
        fout << dist[i] << ' ';
    }
    return 0;
}