record

思路：使用 prim 从 $1$ 结点开始搜索，能走的就走，用 $d$ 数组存到达 $u$ 的最小边，一直找最小边。

#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;
const int N = 3e6 + 5;

struct O{
	int u, v, z;
	friend bool operator < (O x, O y){
		return x.z > y.z;
	}
};

int n, m;
int a[N], p[N], vis[N];
int d[N];// 表示来到点的花费 

vector<O> g[N];

int get(int x){
	if(x == p[x])	return x;
	return p[x] = get(p[x]);
}

signed main(){
	cin>>n>>m;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		p[i] = i;
	}
	for(int i = 1;i <= m;i++){
		int u, v, z;
		cin>>u>>v>>z;
		if(a[v] <= a[u]){
			g[u].push_back({u, v, z});// 判断能走的边 
//			cout<<u<<" "<<v<<" "<<z<<"cnm1\n";
		}
		if(a[u] <= a[v]){
			g[v].push_back({v, u, z});
//			cout<<v<<" "<<u<<" "<<z<<"cnm2\n";
		}
	}
	priority_queue<O> q;
	ll sum = 0, ans = 1;
	vis[1] = 1;
	for(auto v : g[1]){
		q.push({v.u, v.v, v.z});// 把 1 结点的临边加进来。 
	}
	while(!q.empty()){// 堆优化的prim 
		O t = q.top();
		q.pop();
//		cout<<t.u<<" "<<t.v<<"t\n";
		if(d[t.v] <= t.z && vis[t.v])	continue;
		/*
		d 数组的定义是要存到达 i 结点的最小边 
		*/ 
//		if(vis[t.v])	continue;
		
		if(!vis[t.v])	ans++;
		
		sum -= d[t.v];
		sum += t.z;// 选择更好的 
		
		d[t.v] = t.z;
		vis[t.v] = 1;
		
//		cout<<d[t.v]<<"\n";
		
		for(auto v : g[t.v]){// 加边 
			if(v.v == t.u)	continue;// 如果搜出来的边是转移过来的边，就continue，不能搜索到父亲
			if(d[v.v] > v.z || !vis[v.v]){// 有更好的边就用，vis[i]表示有没有被使用过 
//				cout<<v.v<<" "<<d[v.v]<<"\n";
				q.push(v);
				continue;
			}
		}
	}
	cout<<ans<<" "<<sum<<"\n";
	return 0;
}