1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>
#include <algorithm>
#define N 100000
#define M 1000000
struct {int e,v,w;} edge[(M<<1)+1];
int head[N] = {0}, num = 1;
int heap[M], sz = 0;
void conn(int u,int v,int w) {
    edge[num].e = head[u];
    edge[num].v = v;
    edge[num].w = w;
    head[u] = num++;
}
bool cmp(int a,int b) {return edge[a].w > edge[b].w;}
int main() {
    int n,m,u,v,w,res = 0;
    scanf("%d%d\n",&n,&m);
    for(;m--;) {
        scanf("%d%d%d",&u,&v,&w);
        u--; v--; conn(u,v,w); conn(v,u,w);
    }
    v = --n;
    for(;n--;) {
        u = head[v]; head[v] = 0;
        for(; u; u = edge[u].e) {
            heap[sz++] = u;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX