0pts

#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
int dis[maxn],edge[maxn][maxn],n,f[maxn];
long long ans[maxn];
signed main(){
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>dis[i];
		ans[i]=1;
	}
	ans[n]=1;
	memset(edge,0,sizeof edge);
	memset(f,0,sizeof f);
	int a,b,c;
	while(cin>>a>>b>>c){
		edge[a][b]=c;
		edge[b][a]=c;
	}
	for(int i=0;i<n-1;++i){
		int MAX=INT_MAX,id=i;
		for(int j=0;j<n;++j)
		{
			if(!f[j]&&dis[j]<MAX)
			{
				MAX=dis[j];
				id=j;
			}
		}
		f[id]=1;
		for(int j=0;j<n;++j){
			if(f[j]&&edge[id][j]){
				if(dis[edge[id][j]]==dis[id]+dis[j])
					ans[edge[id][j]]+=ans[id]*ans[j];
				else if(dis[edge[id][j]]>dis[id]+dis[j])
				{
					ans[edge[id][j]]=ans[id]*ans[j];
					dis[edge[id][j]]=dis[id]+dis[j];
				}
			}
		}
	}
	cout<<dis[0]<<' '<<ans[0];
	return 0;
}

ac

#include<bits/stdc++.h>
#define maxn 1010
using namespace std;
int dis[maxn],edge[maxn][maxn],n,f[maxn];
long long ans[maxn];
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>dis[i];
		ans[i]=1;
	}
	ans[n]=1;
	memset(edge,0,sizeof edge);
	memset(f,0,sizeof f);
	int a,b,c;
	while(cin>>a>>b>>c){
		edge[a+1][b+1]=c+1;
		edge[b+1][a+1]=c+1;
	}
	for(int i=1;i<n;++i){
		int MAX=INT_MAX,id=i;
		for(int j=1;j<=n;++j)
		{
			if(!f[j]&&dis[j]<MAX)
			{
				MAX=dis[j];
				id=j;
			}
		}
		f[id]=1;
		for(int j=1;j<=n;++j){
			if(f[j]&&edge[id][j]){
				if(dis[edge[id][j]]==dis[id]+dis[j])
					ans[edge[id][j]]+=ans[id]*ans[j];
				else if(dis[edge[id][j]]>dis[id]+dis[j])
				{
					ans[edge[id][j]]=ans[id]*ans[j];
					dis[edge[id][j]]=dis[id]+dis[j];
				}
			}
		}
	}
	cout<<dis[1]<<' '<<ans[1];
	return 0;
}