Sol

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct d {
    int fu, zi;
};
int c[100010], C, s[100010];
vector<d> g[100010];
int ans, total;
void dfs(int u, int from, int e) {
    total = total + c[u] * e;
    s[u] = c[u];
    for (auto p : g[u]) {
        int v = p.fu, w = p.zi;
        if (v == from)
            continue;
        dfs(v, u, e + w);
        s[u] += s[v];
    }
}
void dfs1(int u, int f, int e) {
    ans = min(ans, e);
    for (auto p : g[u]) {
        int v = p.fu, w = p.zi;
        if (v == f)
            continue;
        dfs1(v, u, e + (C - s[v]) * w - s[v] * w);
    }
}
signed main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> c[i], C += c[i];
    for (int i = 1; i < n; i++) {
        int u, v, l;
        cin >> u >> v >> l;
        g[u].push_back(d{ v, l });
        g[v].push_back(d{ u, l });
    }
    ans = 1e18;
    dfs(1, 0, 0);
    dfs1(1, 0, total);
    cout << ans;
    return 0;
}