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. }