#include <bits/stdc++.h>
#define MAXN 50005

using namespace std;

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

struct relationship {
    int i, len;
};

int n, m;
vector<vector<relationship>> graph;

void read() {
    fin >> n >> m;
    graph = vector<vector<relationship>>(n, vector<relationship>());
    for (int k = 0; k < m; k++) {
        int i, j, len;
        fin >> i >> j >> len;
        graph[i].push_back({ j, len });
        graph[j].push_back({ i, len });
    }
}

void sink(relationship heap[], int& sz, int k) {
    while (2 * k <= sz) {
        int j = 2 * k;
        if (j + 1 <= sz && heap[j + 1].len < heap[k].len)
            j++;
        if (heap[j].len > heap[k].len) 
            break;
        swap(heap[j], heap[k]);
        k = j;
    }
}

void swim(relationship heap[], int k) {
    while (k / 2 && heap[k / 2].len > heap[k].len) {
        swap(heap[k / 2], heap[k]); 
        k /= 2;
    }
}

vector<int> dijkstra() {
    vector<int> d(n, INT_MAX); 

    int sz = 0;
    relationship heap[MAXN];
    heap[++sz] = {0, 0};
    while (n) {
        relationship current = heap[1];
        swap(heap[1], heap[sz--]);
        sink(heap, sz, 1);
        d[current.i] = current.len;

        for (auto& neighbour : graph[current.i]) {
            if (d[neighbour.i] == INT_MAX)  
                continue;
            heap[++sz] = {neighbour.i, current.len + neighbour.len};
            swim(heap, sz);
        }
    }

    return d;
}

void solve() {
    vector<int> d = dijkstra();
    for (int i = 1; i < n; i++)
        fout << (d[i] == INT_MAX ? 0 : d[i]) << ' ';
}

int main() {
    read();
    //solve();
    return 0;
}