#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cstdlib>#include <vector>using namespace std;typedef long long ll;vector<pair<int, ll> > g[205];ll n;void init() {for(int i = 0; i < n; i++) {g[i].clear();}}void ins(int u, int v, ll c) {g[u].push_back(make_pair(v, c));}ll a[205];ll cnt[205], sum[205];void dfs1(int u, int f) {cnt[u] = 1;sum[u] = a[u];for(int i = 0; i < g[u].size(); i++) {int ve = g[u][i].first, vc = g[u][i].second;if(ve == f) continue;dfs1(ve, u);cnt[u] += cnt[ve];sum[u] += sum[ve];}}ll pingj, mcn;ll dp[105][105];inline ll ABS(ll x) {if(x < 0) x = -x;return x;}inline void checkmin(ll &x, ll y) {if(x == -1 || x > y) x = y;}void dfs(int u, int f) {if(cnt[u] == 1) {dp[u][0] = 0;dp[u][1] = 0;return ;}ll d[105][105];memset(d, -1, sizeof(d));d[0][0] = 0;int cc = 0;for(int i = 0; i < g[u].size(); i++) {int v = g[u][i].first;ll co = g[u][i].second;if(v == f) continue;dfs(v, u);for(int j = 0; j <= mcn; j++) {if(d[cc][j] == -1) continue;for(int k = 0; k + j <= mcn && k <= cnt[v]; k++) {if(dp[v][k] == -1) continue;int num = k * (pingj + 1) + (cnt[v] - k) * pingj;ll cost = (ll)ABS(sum[v] - num) * (ll)co + dp[v][k];checkmin(d[cc + 1][k + j], cost + d[cc][j]);}}cc++;}for(int i = 0; i <= mcn; i++) {if(d[cc][i] == -1) continue;checkmin(dp[u][i], d[cc][i]);checkmin(dp[u][i + 1], d[cc][i]); }}int main() {while(~scanf("%d", &n)) {init();for(int i = 0; i < n; i++) {scanf("%lld", &a[i]);}for(int i = 0; i < n - 1; i++) {int u, v;ll c;scanf("%d%d%lld", &u, &v, &c);ins(u, v, c);ins(v, u, c);}dfs1(0, -1);pingj = sum[0] / n;mcn = sum[0] - pingj * n;memset(dp, -1, sizeof(dp));dfs(0, -1);printf("%lldn", dp[0][mcn]);}return 0;}
