Bandwidth Management

You are the network administrator of the shake! contest. Every network use is handled by registering a reservation in a queue and receiving your approval.

Surprisingly, the network is a graph with a tree structure. Each vertex of the network is numbered from $1$ to $N$, and every edge is bidirectional.

Each reservation is written as $x,y,w$. The initial bandwidth usage of every vertex is $0$. When a reservation is approved, the bandwidth usage of every vertex on the shortest path between vertex $x$ and vertex $y$ increases by $w$. The shortest path includes both endpoints $x$ and $y$.

Each vertex has a bandwidth limit. If a vertex uses too much bandwidth, the whole server goes down, and as an administrator you cannot accept that. In other words, no vertex's bandwidth usage may exceed its limit. The queue order matters, so you cannot approve a later reservation without approving the earlier ones. For example, you may accept reservations 1, 2, and 3, or accept none of them. You cannot accept only reservations 1 and 3, or only reservations 2 and 3.

Find the maximum number of reservations that can be approved.

The first line contains the number of vertices $N$ and the number of reservations $M$, separated by a space. $(2\le N,M\le 100\,000)$

The next $N-1$ lines each contain two vertices $u$ and $v$ connected by an edge, separated by a space. $(1\le u,v \le N; u\ne v)$

The next line contains $N$ integers $A_1,A_2,\dots,A_N$, separated by spaces. $A_i$ is the bandwidth limit of vertex $i$. $(0\le A_i\le10^9)$

The next $M$ lines each contain integers $x,y,w$ describing a reservation, in the order they were added to the queue. If the reservation is approved, the bandwidth usage of every vertex on the shortest path between vertex $x$ and vertex $y$ increases by $w$. $(1\le w\le 10^9; 1\le x,y\le N)$

The network given in the input is a tree.

Print the maximum number of reservations that can be approved, as a single integer.