1. #include <cstdio>
    2. #include <algorithm>
    3. #include <queue>
    4. #include <cstdlib>
    5. #include <cstring>
    6. #include <iostream>
    7. #define int long long
    8. using namespace std;
    9. inline int gi(){char tmp=getchar();int ans=0;while(!isdigit(tmp))tmp=getchar();while(isdigit(tmp)){ans=ans*10+tmp-'0';tmp=getchar();}return ans;}
    10. int n;
    11. const int N = 1020000;
    12. struct Edg{int v,w,nxt;}Edge[N<<1];int Head[N];
    13. inline void Add(int u,int v,int w){static int cnt=0;Edge[++cnt].v=v;Edge[cnt].nxt=Head[u];Head[u]=cnt;Edge[cnt].w=w;}
    14. struct Nod{
    15. int pos,dis;
    16. bool operator > (const Nod &x)const{
    17. return dis > x.dis;
    18. }
    19. };
    20. int Dis[N],Vis[N];
    21. priority_queue<Nod,vector<Nod>,greater<Nod> > Q;
    22. inline void Pu(int pos,int dis){
    23. Nod p;p.pos=pos;p.dis=dis;
    24. Q.push(p);
    25. }
    26. int Ans[N];
    27. void Dij(){
    28. while(!Q.empty()){
    29. int pos=Q.top().pos;Q.pop();
    30. if(Vis[pos]) continue;
    31. // Ans[pos] = Ans[pos] - (Ans[pos]>>1ll);
    32. Vis[pos] = 1;
    33. for(int i=Head[pos];i;i=Edge[i].nxt){
    34. int arr = Edge[i].v,w=Edge[i].w;
    35. if(Vis[arr]==0)continue;
    36. if(Dis[pos] + Dis[arr] == Dis[w]){
    37. Ans[w] += Ans[pos] * Ans[arr];
    38. }
    39. if(Dis[pos] + Dis[arr] < Dis[w]){
    40. Ans[w] = Ans[pos] * Ans[arr];
    41. Dis[w] = Dis[pos] + Dis[arr];
    42. Pu(w,Dis[w]);
    43. }
    44. }
    45. }
    46. }
    47. signed main()
    48. {
    49. #ifdef TSUKIAKIOI
    50. freopen("data.in","r",stdin);
    51. #endif
    52. int n=gi();
    53. for(int i=1;i<=n;++i) {Dis[i]=gi();Pu(i,Dis[i]);Ans[i]=1;}
    54. int a,b,c;
    55. while(~scanf("%lld%lld%lld",&a,&b,&c)){
    56. a++,b++,c++;
    57. Add(a,b,c);
    58. if(a==b) continue;
    59. Add(b,a,c);
    60. }
    61. Dij();
    62. printf("%lld %lld",Dis[1],Ans[1]);
    63. return 0;
    64. }