맛집 추천

KOI나라에는 $N$개의 도시가 있다. 각 도시에는 1번부터 $N$번까지의 번호가 붙어 있다.

KOI나라의 도로망은 도시를 정점으로, 도로를 양방향 간선으로 나타내면 트리가 된다. 트리는 사이클이 없는 연결 그래프이다.

맛집은 모두 $M$개이며, 1번부터 $M$번까지 번호가 붙어 있다. 맛집이 없는 도시도 있고, 맛집이 두 개 이상 있는 도시도 있다.

$i$번 맛집($1 \le i \le M$)은 $c_i$번 도시에 있고, 배달 가능 거리는 $d_i$, 고객 선호도는 $g_i$이다. $i$번 맛집은 $c_i$번 도시에서 $d_i$개 이하의 도로를 거쳐 갈 수 있는 도시에만 배달할 수 있다. $R_i = \{j \mid d(c_i, j) \le d_i\}$를 $i$번 맛집이 배달할 수 있는 도시의 집합이라고 하자. 여기서 $d(a, b)$는 $a$번 도시와 $b$번 도시 사이의 최단 경로 길이, 즉 두 도시 사이를 이동하는 데 거쳐야 하는 도로의 최소 개수이다.

당신은 배달 앱의 운영자이다. 서비스가 겹치지 않도록, $M$개의 맛집 중에서 다음 조건을 만족하는 맛집의 집합 $S$를 고르려고 한다. 어느 도시도 $S$에 속한 두 개 이상의 맛집의 배달 가능 집합에 동시에 속하지 않아야 한다. 즉, $S$에 속한 서로 다른 두 맛집 $i$와 $j$에 대해 $R_i \cap R_j = \emptyset$이다.

조건을 만족하는 집합 $S$ 중에서 선호도의 합이 가장 큰 집합을 찾아, 그때의 선호도 합을 출력하라.

첫 번째 줄에 두 정수 $N$과 $M$이 공백 하나를 사이에 두고 주어진다.

다음 $N-1$개의 줄에는 도시 사이의 길을 나타내는 두 정수 $a$와 $b$가 공백 하나를 사이에 두고 주어진다.

다음 $M$개의 줄에는 맛집 정보가 주어진다. $i$번째 줄($1 \le i \le M$)에는 세 정수 $c_i$, $d_i$, $g_i$가 공백 하나를 사이에 두고 주어진다.

첫 번째 줄에 조건을 만족하는 집합 $S$ 중 선호도 합의 최댓값을 출력한다.

• 주어지는 모든 수는 정수이다.
• $1 \le N \le 10^5$
• $1 \le M \le 10^5$
• 모든 $i$($1 \le i \le M$)에 대해 $0 \le d_i \le N - 1$, $1 \le g_i \le 10^9$