1003 Emergency 25

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
const int maxn = 505;
int G[maxn][maxn],rescueNum[maxn],vis[maxn]={0},dis[maxn],teamNum[maxn]={0},pathNum[maxn]={0};
int n,m,s,e,INF=1000000000;

int findNotVisMin(){
    int minIdx = -1;
    int minDis = INF;
    for(int i = 0; i < n; i++){
        if(vis[i] == 0 && dis[i] < minDis){
            minIdx = i;
            minDis = dis[i];
        }
    }
    return minIdx;
}
int main() {
    scanf("%d%d%d%d", &n, &m, &s, &e);
    int tmp,from,to,weight;
    for(int i = 0; i < n; i++){
        scanf("%d", &tmp);
        rescueNum[i] = tmp;
    }
    fill(G[0], G[0]+maxn*maxn, INF);
    for(int i = 0; i < m; i++){
        scanf("%d%d%d", &from, &to, &weight);
        G[from][to] = G[to][from] = weight;
    }
    fill(dis, dis+maxn, INF);
    dis[s] = 0;
    teamNum[s] = rescueNum[s];
    pathNum[s] = 1;
    for(int i = 0; i < n; i++){
        int min = findNotVisMin();
        if(min == -1) break;
        vis[min] = 1;
        for(int j = 0; j < n; j++){
            if(vis[j] == 0 && G[min][j] != INF){
                if(dis[min]+G[min][j] < dis[j]){
                    dis[j] = dis[min]+G[min][j];
                    pathNum[j] = pathNum[min];
                    teamNum[j] = teamNum[min] + rescueNum[j];
                }else if(dis[min]+G[min][j] == dis[j]){
                    pathNum[j] += pathNum[min];
                    if(teamNum[min]+rescueNum[j] > teamNum[j]){
                        teamNum[j] = teamNum[min]+rescueNum[j];
                    }
                }
            }
        }
    }
    printf("%d %d\n", pathNum[e], teamNum[e]);
    return 0;
}