P1875
参考第二篇题解，依照自己的习惯写的qwq
36pts

#include <bits/stdc++.h>

using namespace std;

struct E {
	int u2, v, nxt;
}e[1000006];
int head[1003], cnt = 1;

int n, cost[1003];

void add(int u1, int u2, int v) {
	e[++cnt] = {u2, v, head[u1]};
	head[u1] = cnt;
}

void build() {
	int a, b, c;
	while(cin >> a && a) {
		cin >> b >> c;
		add(a, b, c);
		if (a == b) continue;
		add(b, a, c);
	}
}

int path[1003];
bool vis[1003];
priority_queue<pair<int, int>> q;

void dijstra() {
	while (!q.empty()) {
		int u = q.top().second;
		int d = -q.top().first;
		q.pop();
		if (d != cost[u]) continue;
		vis[u] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v, u2 = e[i].u2;
			if (vis[u2]) {
				if (cost[v] > d + cost[u2]) {
					cost[v] = d + cost[u2];
					path[v] = path[u] * path[u2];
					q.push({-cost[v], v});
				}
				else if (cost[v] == d + cost[u2]) {
					path[v] += path[u] * path[u2];
				}
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> cost[i], q.push({-cost[i], i}), path[i] = 1;
	build();
	dijstra();
	cout << cost[0] << ' ' << path[0] << '\n';
	return 0;
}