Untitled

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn = 100100;
const int maxm = 200100;
struct node {
    int id, fa;
    long long len;
    bool operator < (const node &p) const {
        return len < p.len || len == p.len && id < p.id;
    }
} a[maxn];
struct edge {
    int next, to, len;
} e[maxm * 2];
set<node> T;
int h[maxn], tot = 0;
int n, m;
void add(int x, int y, int z) {
    e[++tot] = (edge){h[x], y, z};
    h[x] = tot;
}
int main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    int x, y, z;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
        add(y, x, z);
    }
    for (int i = 1; i <= n; i++) {
        a[i].id = i;
        a[i].fa = -1;
        a[i].len = 1ll << 60;
    }
    a[1].len = 0;
    T.insert(a[1]);
    while(!T.empty()) {
        node tmp = *T.begin();
        T.erase(T.begin());
        for (int i = h[tmp.id]; i; i = e[i].next) {
            int to = e[i].to;
            if (a[to].len > tmp.len + e[tmp.id].len || a[to].len == tmp.len + e[tmp.id].len && a[to].fa > tmp.id) {
                T.erase(a[to]);
                a[to].len = tmp.len + e[tmp.id].len;
                a[to].fa = tmp.id;
                T.insert(a[to]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = h[i]; j; j = e[j].next) {
            int to = e[j].to;
            if (a[i].len + e[j].len == a[to].len) {
                a[to].fa = min(a[to].fa, i);
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        cout << a[i].fa << ' ';
    }
    return 0;
}