24889번 - 통행량 조사

문제

숭고한 나라에는 1ドル$번부터 $N$번까지의 번호가 붙어 있는 $N$개의 도시가 있다. 또한, 한양대학교가 있는 수도권 지하철 2호선의 모습을 본떠 1ドル$번부터 $N$번까지의 번호가 붙어 있는 $N$개의 도로가 있다. 각 도로는 서로 다른 두 도시를 연결하고, 같은 도로는 여러 개 존재하지 않는다. 즉, 숭고한 나라의 도로망은 단순 그래프 형태이다. 또한 모든 도시는 도로를 통해 서로 이동할 수 있다.

현대모비스에 입사한 정휘는 효율적인 자율주행 소프트웨어 개발을 위해 각 도로의 통행량을 분석하는 업무를 맡게 되었다. 구체적으로, 여러분은 차량 집단 $M$개의 출발 도시와 도착 도시가 주어지면 각 도로를 지나는 차량의 개수를 구해야 한다.

$i$번째 차량 집단은 $w_i$대의 차량으로 구성되어 있으며, 출발 도시에서 도착 도시까지 각 도시와 도로를 최대 한 번 사용해서 이동한다. 이때 출발 도시에서 도착 도시까지 가는 경로가 여러 개 존재할 수 있는데, 최악의 경우를 고려해야 하므로 차량 집단이 이용할 가능성이 있는 모든 도로에 $w_i$대의 차량이 지나는 것으로 계산해야 한다. 다시 말해, 각 도로를 지날 가능성이 있는 차량의 수를 구해야 한다.

정휘는 이 문제를 $O(NM)$ 시간에 해결했지만 더 효율적인 방법이 궁금해서 입사 선배인 당신에게 도움을 요청했다. 정휘를 도와 문제를 효율적으로 해결해 보자.

입력

첫째 줄에 도시와 도로의 수 $N$과 차량 집단의 수 $M$이 주어진다. (3ドル \leq N \leq 200,000,円\ 1 \leq M \leq 200,000円$)

둘째 줄부터 $N$개의 줄에 $i$번 도로가 연결하는 두 도시의 번호 $a_i,\ b_i$가 주어진다. (1ドル \leq a_i,b_i \leq N,\ a_i \neq b_i$)

다음 $M$개의 줄에 $i$번 차량 집단의 출발 도시, 도착 도시, 차량 대수 $s_i, e_i, w_i$가 주어진다. (1ドル \leq s_i,e_i \leq N,\ 1 \leq w_i \leq 5,000,円\ s_i \neq e_i$)

연결하는 도시 쌍이 동일한 도로가 여러 개 주어지지 않고, 임의의 두 도시는 도로를 통해 서로 이동할 수 있다.

출력

$N$개의 줄에 걸쳐 정답을 출력한다.

$i$번째 줄에 $i$번째 도로를 통과할 가능성이 있는 차량의 수를 출력한다.

제한

힌트