#include <bits/stdc++.h>
using namespace std;

struct FastIO
{
    inline FastIO& operator >> (int& x) {
        x = 0; char f = 0, ch = getchar();
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (long long& x) {
        x = 0; char f = 0, ch = getchar();
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (__int128& x) {
        x = 0; char f = 0, ch = getchar();
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        return x = (f ? -x : x), *this;
    }
    inline FastIO& operator >> (double& x) {
        x = 0; char f = 0, ch = getchar();
        double d = 0.1;
        while(ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
        while(ch <= '9' && ch >= '0') x = x * 10 + ch - 48, ch = getchar();
        if(ch == '.')
        {
            ch = getchar();
            while(ch <= '9' && ch >= '0') x += d * (ch ^ 48), d *= 0.1, ch = getchar();
        }
        return x = (f ? -x : x), *this;
    }
}rin;

const int N = 1e5 + 10;

int id, n, t, s[N];

// 链式前向星
int to[N << 1], head[N << 1], nxt[N << 1], w[N << 1], w_[N << 1];
int totE;
inline void init() {
    totE = 0;
    memset(head, -1, sizeof(head));
}
inline void addDirEdge(const int& u, const int& v, const int& _w, const int& _w_) {
    nxt[++totE] = head[u];
    head[u] = totE;
    to[totE] = v;
    w[totE] = _w;
    w_[totE] = _w_;
}
inline void addEdge(const int& u, const int& v, const int& _w, const int& _w_) {
    addDirEdge(u, v, _w, _w_);
    addDirEdge(v, u, _w, _w_);
}

// 计算子树大小 计算初始答案
__int128 orgAns;
long long sz[N], sum;
inline void dfs1(int u = 1, int fa = -1) {
    sz[u] = s[u];
    for (int i = head[u]; i != -1; i = nxt[i]) {
        if (to[i] != fa) {
            dfs1(to[i], u);
            sz[u] += sz[to[i]];
            orgAns += (__int128)sz[to[i]] * (sum - sz[to[i]]) * w[i];
        }
    }
}

// 凸包
struct Point {
    __int128 x, y;
};
inline bool operator <(const Point& pA, const Point& pB)  {
    return pA.x == pB.x? pA.y < pB.y : pA.x < pB.x;
}
inline bool operator ==(const Point& pA, const Point& pB) {
    return pA.x == pB.x;
}
inline __float128 slope(const Point& pA, const Point& pB) {
    return (__float128)(pA.y - pB.y) / (pA.x - pB.x);
}
int totP;
int l, r, q[N];
Point p[N];

// DP
__int128 dp[N], Mx;
inline void dfs2(int u = 1, int fa = -1, __int128 e = 0) {
    dp[u] = e;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        if (to[i] != fa) {
            dfs2(to[i], u, (__int128)sz[to[i]] * (sum - sz[to[i]]) * (w[i] - w_[i] - t));
            if (fa != -1) dp[u] = max(dp[u], e + dp[to[i]] + (__int128)sz[to[i]] * (sum - sz[u]) * t);
            Mx = max(Mx, dp[u]);
        } 
    }

    totP = 0;
    for (int i = head[u]; i != -1; i = nxt[i]) {
        if (to[i] != fa) {
            p[++totP] = (Point){sz[to[i]], dp[to[i]]};
        }
    }

    sort(p + 1, p + totP + 1);
    
    for (int i = 1; i + 1 <= totP; ++i) {
        if (p[i] == p[i + 1]) {
            Mx = max(Mx, p[i].y + p[i + 1].y + p[i].x * p[i + 1].x * t);
        }
    }

    int curP = unique(p + 1, p + totP + 1) - p - 1;

    q[l = r = 1] = 1;
    for (int i = 2; i <= curP; ++i) {
        while (l < r && slope(p[q[l]], p[q[l + 1]]) >= -t * p[i].x) ++l;
        Mx = max(Mx, p[i].y + p[q[l]].y + p[i].x * p[q[l]].x * t);
        while (l < r && slope(p[q[r - 1]], p[q[r]]) <= slope(p[q[r]], p[i])) --r;
        q[++r] = i;
    }
}

// 输出
inline void output(__int128 ans) {
    string str;
    if (!ans) {
        str = "0";
    } else {
        str = "";
        while (ans) {
            str = ((char)('0' + ans % 10)) + str;
            ans /= 10;
        }
    }
    cout << str << endl;
}

// 解决问题
void solve() {
    dfs1();
    dfs2();
    orgAns -= Mx;
    output(orgAns);
}

signed main() {
    rin >> id >> n >> t;
    for (int i = 1; i <= n; ++i) {
        rin >> s[i];
        sum += s[i];
    }
    init();
    for (int i = 1, u, v, w, w_; i < n; ++i) {
        rin >> u >> v >> w >> w_;
        addEdge(u, v, w, w_);
    }
    solve();
    return 0;
}

WA 一个点，求调。