记录编号	545472	评测结果	AAAAAAAAAA
题目名称	[WZOI 2011 S3] 周年纪念日	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.450 s
提交时间	2019-10-29 21:45:25	内存使用	47.23 MiB

#include<bits/stdc++.h>
#define I inline
#define LL long long
#define int LL
using namespace std;
const int N=2e5+7;
struct edge
{
	int nx,to,from;
	LL dis;
} e[N<<1],le[N<<1];
bool cmp(edge a,edge b)
{
	return a.dis<b.dis;
}
LL dep[N],size[N],ans[N],p[N];
LL cost,tim,S;
int cnt,row,tot,n,m;
int fa[N],head[N];
int find(int x)
{
	if (fa[x]!=x) return fa[x]=find(fa[x]);
	else return fa[x];
}
I int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
void add_edge(int a,int b,int dist)
{
	cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dis=dist;head[a]=cnt;
}
void dfs(int x,int ff)
{
	size[x]=p[x];
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==ff) continue;
		dfs(y,x);
		size[x]+=size[y];
	}
}
void calc(int x,int ff,LL dep)
{
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==ff) continue;
		ans[1]+=p[y]*(dep+e[i].dis);
		calc(y,x,dep+e[i].dis);
	}
}
void DP(int x,int fa)
{
	for (int i=head[x];i;i=e[i].nx)
	{
		int y=e[i].to;
		if (y==fa) continue;
		ans[y]=ans[x]-e[i].dis*size[y];
		DP(y,x);
	}
}
signed main()
{
	freopen("anniversary.in","r",stdin);
	freopen("anniversary.out","w",stdout);
	//freopen("xx.in","r",stdin);
	n=read();m=read();
	for (int i=1;i<=n;i++) p[i]=read(),S+=p[i];
	for (int i=1;i<=m;i++)
	{
		LL x=read(),y=read(),z=read();
		le[i].from=x;le[i].to=y;le[i].dis=z;
	}
	for (int i=1;i<=n;i++) fa[i]=i;
	sort(le+1,le+m+1,cmp);
	for (int i=1;i<=m;i++)
	{
		int x=le[i].from,y=le[i].to;
		int fx=find(x),fy=find(y);
		if (fx==fy) continue;
		cost+=le[i].dis;tim=max(tim,le[i].dis);
		add_edge(x,y,le[i].dis);add_edge(y,x,le[i].dis);
		fa[fx]=fy;tot++;
		if (tot==n-1) break;
	}
	printf("%lld %lld\n",cost,tim);
	dfs(1,0);for (int i=1;i<=n;i++) size[i]=2*size[i]-S;
	calc(1,0,0);DP(1,0);
	LL out=5e18+7;int pos;
	for (int i=1;i<=n;i++) if (ans[i]<=out) pos=i,out=ans[i];
	printf("%lld %lld\n",pos,out);
	return 0;
}