class Solution {
    typedef long long int ll;
    
    vector<vector<vector<int>>> adj;
    vector<int> vis;
    int ans;
    
private:
    void dfs(int cur, int score, vector<int>& val, int maxi, int tot) {
        
        if (tot > maxi)
            return;
        
        if (!vis[cur])
            score += val[cur];
        
        vis[cur]++;
       
        if (cur == 0)
            ans = max(ans, score);
        
        for (auto x : adj[cur])
            dfs(x[0], score, val, maxi, tot + x[1]);
        
        vis[cur]--;
    }

public:
    int maximalPathQuality(vector<int>& val, vector<vector<int>>& edges, int maxi) {
        int n = val.size();
        
        adj = vector<vector<vector<int>>>(n);
        vis = vector<int>(n, 0);
        for (auto x : edges) {
            adj[x[0]].push_back({x[1], x[2]});
            adj[x[1]].push_back({x[0], x[2]});
        }
        
        // ans = 0;
        ans = val[0];
        // vis[0] = 1;
        dfs(0, 0, val, maxi, 0);
        
        return ans;
    }
};