Marisa, after brewing potions, proceeds to sell them. The Human Village can be visualized as a tree of $n$ vertices, where each vertex represents a house. House $i$ has a maximum purchasing limit of $A_i$ bottles from Marisa. Over the next $k$ days, Marisa plans to transport $c_i$ bottles and sell them along the simple path connecting houses $u_i$ and $v_i$. What is the maximum number of potion bottles she can sell in $k$ days?
### Input
- The first line contains two integers $n,k$.
- The second line contains $n$ integers $A_i$.
- The next $n - 1$ lines, each line contains two integers $u,v$, there is an edge between $u$ and $v$.
- The next $k$ lines, each line contains three integers $u_i,v_i,c_i$.
### Output
- Print the maximum number of potion bottles Marisa can sell.
### Constraints
- $1 \le n, k \le 10^4$.
- $0 \le A_i \le 10^5$.
- $1 \le u, v \le n$.
- $1 \le c_i \le 10^5$.
### Example
Input:
```
4 2
0 1 2 2
1 4
2 4
3 4
1 2 2
1 3 3
```
Output:
```
5
```
