Maximum Sum Connected Subgraph Under Weight Constraint

You are given an undirected graph with N nodes and M edges. Each node i has an associated value V_i. Each edge connects two nodes and has a weight. Your task is to determine the maximum possible sum of node values for any connected subgraph such that the sum of the weights of the edges in the subgraph does not exceed K.

Formally, let the subgraph have a set of nodes S and a set of edges E'. It must be connected, and it should satisfy the condition:

\(\sum_{e \in E'} w_e \le K\)

Your goal is to maximize the sum \(\sum_{i \in S} V_i\). If it is not possible to select any connected subgraph under the constraint, output 0.

Note: The nodes are numbered from 1 to N.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains three integers: N (number of nodes), M (number of edges) and K (maximum allowed total weight).
2. The second line contains N integers where the i-th integer represents the value V_i of node i.
3. The following M lines each contain three integers: A, B, and W, representing an edge between nodes A and B with weight W.

outputFormat

Output a single integer to stdout, which is the maximum sum of node values in any connected subgraph that satisfies the weight constraint.

4 4 10
1 2 3 4
1 2 3
2 3 4
3 4 2
4 1 5

10