통행량 조사

숭고한 나라에는 $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$번째 도로를 통과할 가능성이 있는 차량의 수를 출력한다.