31234번 - 대역폭 관리

문제

당신은 shake! 대회의 네트워크 관리자다. 모든 네트워크의 사용은 예약 큐에 등록 후 당신의 승인을 받아 이루어진다.

놀랍게도 네트워크는 트리 구조의 그래프이다. 네트워크의 각 정점은 1ドル$번부터 $N$번까지 번호가 부여되어 있고, 모든 간선은 양방향이다.

각 예약은 $x,y,w$로 표현된다. 각 정점의 초기 대역폭 사용량은 0ドル$이며, 어떤 예약이 승인되면 $x$번 정점과 $y$번 정점을 잇는 최단 경로에 포함되는 모든 정점의 대역폭 사용량이 $w$만큼 증가한다. 이때 최단 경로는 양 끝의 $x$번 정점과 $y$번 정점을 포함한다.

그런데 각 정점은 한계 대역폭이 있어 대역폭을 과다하게 사용하면 전체 서버가 다운된다. 이것은 네트워크 관리자로서 용납할 수 없는 일이다. 즉, 어떤 정점의 대역폭 사용량도 그 정점의 한계 대역폭을 넘으면 안 된다. 또한 큐의 순서는 중요하기 때문에, 앞선 예약을 받지 않고 이후 예약을 승인할 수 없다. 예를 들어 1ドル$번, 2ドル$번, 3ドル$번 예약을 받거나 아무 예약도 받지 않을 수 있지만, 1ドル$번, 3ドル$번 예약만 받거나 2ドル$번, 3ドル$번 예약만 받을 수는 없다.

승인할 수 있는 최대 예약 수를 구해보자.

입력

첫째 줄에 네트워크의 정점 개수 $N$과 예약 개수 $M$이 공백으로 구분되어 주어진다. $(2\le N,M\le 100,000円)$

다음 $N-1$개의 줄에 네트워크의 각 간선이 잇는 두 정점의 번호 $u, v$가 공백으로 구분되어 주어진다. $(1\le u,v \le N; u\ne v)$

다음 줄에 $N$개의 정수 $A_1,A_2,\dots,A_N$이 공백으로 구분되어 주어지며, 이때 $A_i$는 $i$번 정점의 한계 대역폭이다. $(0\le A_i\le10^9)$

다음 $M$개의 줄에 각 예약을 표현하는 정수 $x,y,w$가 공백으로 구분되어 큐에 등록된 순서대로 주어진다. 이는 예약을 승인하면 $x$번 정점과 $y$번 정점을 잇는 최단 경로에 포함되는 모든 정점의 대역폭 사용량이 $w$만큼 증가하는 것을 의미한다. $(1\le w\le 10^9; 1\le x,y\le N)$

입력으로 주어지는 네트워크는 트리 구조이다.

출력

승인할 수 있는 최대 예약 수를 하나의 정수로 출력한다.

제한

힌트