7C

#include <stdio.h>
#include <set>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    freopen("pathbgep.in", "r", stdin);
    freopen("pathbgep.out", "w", stdout);
    long long n, m;
    const long long SIZE = 30000, INFINITY = (const long long int) 1e17;
    scanf("%lld %lld", &n, &m);
    vector<pair<int, int>> adjacencyLis[SIZE];
    for (int i = 0; i < m; ++i) {
        long long vertex1, vertex2, weight;
        scanf("%lld %lld %lld", &vertex1, &vertex2, &weight);
        adjacencyLis[vertex1 - 1].push_back({vertex2 - 1, weight});
        adjacencyLis[vertex2 - 1].push_back({vertex1 - 1, weight});
    }
    vector<long long> d(n, INFINITY);
    vector<bool> vst(n, false);
    d[0] = 0;
    set<pair<long long, long long>> s;
    s.insert({0, 0});
    for (int i = 0; i < n && s.size(); ++i) {
        auto p = *s.begin();
        long long int v = p.second;
        s.erase(p);
        vst[v] = true;
        for (auto to: adjacencyLis[v]) {
            if (d[to.first] > d[v] + to.second) {
                s.erase({d[to.first], to.first});
                d[to.first] = d[v] + to.second;
                s.insert({d[to.first], to.first});
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        printf("%lld ", d[i]);
    }
    return 0;
}