5294: Gas Station

ZYT loves driving. One day he found some islands, and wanted to go on a tour.

These n islands are connected  by n−1 bi-directed roads. The i^th road connects island u_i, v_i , and takes w_i liter(s) of gasoline to pass. And on each island there is a gas station, which can add at most a_i liter(s) of gasoline to his car.

ZYT has q plans, the i^th is that:

1. He will start from x_i, and has d_i liter(s) of gasoline initially.
2. There's an island p_i he does not like to pass in this plan.

For each plan, he wants to know how many different islands he can reach in this plan(including x_i). We say he can reach the island y if and if only there exists a available simple path starts from x_i and ends at y, and he always has at least 0 liter of gasoline during the whole tour.

A simple path is a path that passes each island at most once.

The first line of input contains two integers n, q — number of islands, number of tour plans.

Then n−1 lines ,each line containing three integers u_i, v_i, w_i, describing a road.

Then a line with n integers a₁,a₂,⋯,a_n — the gas stations' fuel limits.

Last q lines, each contains three integers x_i, d_i, p_i, describing a tour plan.

Output q lines — the number of reachable islands in each plan.

5 5
1 2 9
1 3 1
3 4 10
1 5 2
7 2 2 2 2 
2 7 4
2 2 3
1 5 4
3 6 5
3 0 2

4
1
4
3
3

It's guaranteed that n≤100000,q≤100000,1≤a_i,w_i≤10⁹,1≤x_i,u_i,v_i≤n,0 ≤d_i≤10¹⁴,p_i ≠ x_i.