대역폭 관리

당신은 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)$

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

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