통행량 조사

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

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

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

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

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