/* 题目大意为：在只能从点权大的点到点权小的点（可以相等）的情况下，从1点出发建立一棵尽可能有更多点的最小生成树

显然我们不能直接求最小生成树，因为有些点应为高度原因无法到达。

为保证我们只会由高到低，我们就只建立由高向低的单向边即可。

对于建立出来的图A，由1点开始宽搜，将扩展到的点和边加入一个新图B，所有扩展到的点便是能到达的最多点。

我们再在这个新图上跑Kruskal求最小生成树，求得最短距离。

对于排序部分，为保证有尽可能多的点在最小生成树里，我们按终点的高度为第一关键字从大到小排序，边长为第二关键字从小到大排序；

这样就能保证拓展的点最多，进而再用最小生成树求最短距离。

*/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define R register
#define Rf(a,b,c) for(R int (a)=(b);(a)<=(c);++(a))
#define Tf(a,b,c) for(R int (a)=(b);(a)>=(c);--(a))
using namespace std;
const int N=2000000+5,M=100000+5;
ll n,m,tot,ans,num,sum,cnt,ql,qr;
struct it{
    ll u,v,w;//新图 
};
struct node {
    ll to,nx,val;//初始图（链式前向星） 
};
it a[N];node b[N];
ll fa[M],h[M],head[M],q[M];
bool vis[M];
inline ll read()//读入优化 
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x*=10;x+=(ch-'0');ch=getchar();}
    return x*f;
}
bool cmp1(it x,it y) {
//比较函数，以终点的高度为第一关键字从大到小排序，边长为第二关键字从小到大排序 
    if(h[x.v]!=h[y.v]) return h[x.v]>h[y.v];
    return x.w<y.w;
}
inline ll find(ll x) {//并查集找父亲 
    if(fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
inline void add(int u,int v,int c) {//链式前向星加边 
    b[++num].to=v;
    b[num].nx=head[u];
    head[u]=num;
    b[num].val=c;
}
void bfs(){//宽搜，拓展可到达的点，建新图 
    q[++qr]=1;vis[1]=1;
    while(ql<qr) {
        int now=q[++ql];
        for(int i=head[now];i;i=b[i].nx) {
            a[++cnt].u=now;a[cnt].v=b[i].to;a[cnt].w=b[i].val;//建立新图的边 
            if(!vis[b[i].to]) {
                vis[b[i].to]=1;sum++;//sum计数器计可到达的点 
                q[++qr]=(b[i].to);
            }
        }
    }
}
int main()
{
//    freopen("steep.in","r",stdin);
//    freopen("steep.out","w",stdout);
    n=read();m=read();//读入数据 
    Rf(i,1,n) h[i]=read(),fa[i]=i;
    Rf(i,1,m) {
        R int u=read(),v=read(),c=read();
        if(h[u]>=h[v]) add(u,v,c);//根据边两边的点的高度，建立一条由高到低的单向边 
        if(h[u]<=h[v]) add(v,u,c);//当高度相等时会建两条边 
    }
    bfs();//广搜拓展点 
    sort(a+1,a+1+cnt,cmp1);//对新图的点跑Kruskal求最小生成树 
    Rf(i,1,cnt) {
        R int rx=find(a[i].u),ry=find(a[i].v);
        if(rx!=ry) {
            fa[rx]=ry;ans+=a[i].w;//求最短距离 
        }
    }
    printf("%lld %lld",sum+1,ans);//sum+1，还有初始的1点可到 
    return 0;
}

题意简述：在一个只能沿着边从点权大的点向点权小的点连边，在这个图在包含的点最多的前提下求边权和最小的生成树。

思路解析：如果将这道题抽象出了题意简述的内容的话，就可以考虑使用 $Kruskal$ 还是 $Prim$ 了。但是由于本蒟蒻不知道在有向边的情况下怎么用 $Kruskal$，所以我就用 $Prim$ 写的这道题。

但这一道题中，看数据范围能够发现显然要用堆优化版的 $Prim$，所以之后重要的就是确定 $Prim$ 的排序关键字了。

我们先假设已经在生成树中的集合叫 $S$,然后想一想，$S$ 中只经过一条边就能到达的结点中，高度最大的我们肯定要取。因为这个结点不可能绕路之后被取到，因为这是高度最大的结点，而我们经过的结点高度肯定是递减的，所以这个命题正确。

这样就满足了条件1，而条件2怎么满足呢？当然就是在满足条件1的情况下按离集合 $S$ 的距离越近越好。

总结一下，也就是说我们的排序有两个关键字，第一关键字是通向的结点的高度，第二关键字是离集合 $S$ 的距离。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int NR=1e5+10;
const int MR=2e6+10; 
const int INF=0x3f3f3f3f;
int n,m;
int a[NR];
int to[MR],nxt[MR],val[MR];
int head[NR];
int tot=1;
void add(int x,int y,int z)
{
	to[tot]=y;
	val[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot++;
}
int ans1;
ll ans2;
bool vis[NR];
int dis[NR];
struct Nd
{
	int x,h,d;
	bool operator <(const Nd &A) const
	{
		if(A.h!=h) return h<A.h;
		return d>A.d;
	}
};
priority_queue<Nd> q;
Nd tmp;
void prim(int s)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	tmp.x=s,tmp.h=a[1],tmp.d=0;dis[s]=0;
	q.push(tmp);
	while(!q.empty())
	{
		int x=q.top().x;
		q.pop();
		if(vis[x]) continue;
		if(dis[x]>=INF) return;
		ans1++,ans2+=1ll*dis[x];vis[x]=1;
		for(int i=head[x];i;i=nxt[i])
		{
			int y=to[i];
			if(dis[y]>val[i]&&!vis[y])
			{
				dis[y]=val[i];
				tmp.x=y,tmp.h=a[y],tmp.d=dis[y];
				q.push(tmp);
			}
		}
	}
}
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=m;i++)
	{
		int x=read(),y=read(),z=read();
		if(a[x]>a[y]) add(x,y,z);
		else if(a[y]>a[x]) add(y,x,z);
		else add(x,y,z),add(y,x,z);
	}
	prim(1);
	printf("%d %lld\n",ans1,ans2);
	return 0;
}

最小生成树prim算法

#include<bits/stdc++.h>
#define int long long
#define setp(x) fixed<<setprecision(x)
using namespace std;
constexpr int N=1e5+10;
int n,m,ans1,ans2;
bool vis[N];
int a[N],dis[N];
vector<pair<int,int>>G[N];
struct node{
	int x,h,d;
	friend bool operator<(const node&x,const node&y){return (x.h==y.h?x.d>y.d:x.h<y.h);}
};
inline void prim(int s){
	priority_queue<node>Q;
	dis[s]=0;
	Q.push({s,a[1],0});
	while(Q.size()){
		int x=Q.top().x;
		Q.pop();
		if(vis[x])continue;
		if(dis[x]>=0x3f3f3f3f)return;
		ans1++;
		ans2+=dis[x];
		vis[x]=true;
		for(auto i:G[x]){
			int y=i.first,z=i.second;
			if(dis[y]>z&&!vis[y]){
				dis[y]=z;
				Q.push({y,a[y],dis[y]});
			}
			
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(dis,0x3f,sizeof dis);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		if(a[x]>a[y])G[x].push_back({y,z});
		else if(a[x]<a[y])G[y].push_back({x,z});
		else G[x].push_back({y,z}),G[y].push_back({x,z});
	}
	prim(1);
	cout<<ans1<<" "<<ans2<<"\n";
	return 0;
}