Description：

每个点有海拔，只能从某个位置滑向海拔小于等于它的位置，可以用技能返回上一个位置，求最多能到几个点以及在走的点最多的情况下最小距离。

$1\leqslant n\leqslant 10^5$

Solution：

题意就是求一个有向图的最小生成树，这个有向图可以有双向边且双向边权相同，除去这些边是一个 $DAG$ 。

求最小树形图有 $O(VE)$ 的朱刘算法，但是这题显然不可以，考虑怎么把无向图最小生成树推广到有向图上，考虑之所以 $prim$ 在无向图上不能用，是因为如果当前这个点是离当前生成树最近的点，那么就会把他加进树中，但是可能之后有另一个把他的距离更新成更短，但是这个只有一个方向，也就是说从另一边选不了这条边，然后 $prim$ 就不能得到正确结果。

然后就有一个神奇方法可以把 $prim$ 应用到这上面，就是用拓扑排序的顺序更新 $prim$ ，因为一个点的入边一定是拓扑排序在他之前的，而且双向边边权相同，所以这样按顺序更新不会有问题，这个题因为有双向边所以可以按高度为第一关键字，距离为第二关键字排序做 $prim$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

} 

int n,m;

#define MAXN 100010

int h[MAXN];

#define MAXM 1000010

struct edge

{

	int to,nxt,v;

}e[MAXM << 1];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b,int v)

{

	if(h[a] >= h[b]){++edgenum;e[edgenum].to = b;e[edgenum].v = v;e[edgenum].nxt = lin[a];lin[a] = edgenum;}

	if(h[b] >= h[a]){++edgenum;e[edgenum].to = a;e[edgenum].v = v;e[edgenum].nxt = lin[b];lin[b] = edgenum;}

	return;

}

int d[MAXN];

bool v[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&h[i]);

	int a,b,c;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	memset(d,0x3f,sizeof(d));

	d[1] = 0;

	priority_queue< pair<pair<int,int>,int> > q;

	q.push(make_pair(make_pair(h[1],0),1));

	memset(v,false,sizeof(v));

	int ans1 = 0;

	long long ans2 = 0;

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(v[k])continue;

		ans1++;ans2 += d[k];

		d[k] = 0;v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > e[i].v)

			{

				d[e[i].to] = e[i].v;

				q.push(make_pair(make_pair(h[e[i].to],-d[e[i].to]),e[i].to));

			}

		}

	}

	cout << ans1 << " " << ans2 << endl;

	return 0;

}