SoleMap

모든 지도는 ‘단 하나’(Sole)로 통한다, 현대오토에버 차세대 내비게이션 지도 ‘SoleMap’

처음 가는 길을 운전할 때 갈림길을 잘못 들거나 차선을 잘못 타서 곤란해하는 사람을 본 적은 누구에게나 한 번쯤 있을 것입니다. 내비게이션이 있어도 초행길에서는 화면과 실제 도로를 머릿속에서 바로 맞춰 보기 어려운 경우가 많습니다. SoleMap은 이런 운전자의 불편을 해소하기 위해 현대오토에버가 구축 중인 차세대 내비게이션 지도입니다. 이름은 ‘단 하나의’라는 뜻의 형용사 Sole에 지도(Map)를 더해 통합의 의미를 담은 것입니다. SoleMap은 2024년 안에 실제 내비게이션에 탑재하는 것을 목표로 하고 있습니다.

직선나라의 도로는 $N$개의 도시가 일직선으로 늘어선 구조입니다. 모든 $1\leq i\leq(N-1)$에 대해 $i$번 도시와 $(i+1)$번 도시는 양방향 $w_{i}$차로 도로로 직접 연결되어 있습니다. 직선나라에는 매일 $u_{j}$번 도시에서 $v_{j}$번 도시까지 이동하는 차량이 $x_{j}$대씩 있습니다. 따라서 직선나라에서는 매일 모두 $\sum_{j}x_{j}$대의 차량이 이동합니다. 두 도시를 잇는 경로는 하나뿐이지만, 어떤 차로를 이용하느냐에 따라 더 빨리 갈 수도, 정체 때문에 더 느리게 갈 수도 있습니다. 차로를 구분하지 않고 경로만 알려 주던 기존 내비게이션은 큰 도움이 되지 못했습니다.

직선나라의 대통령 키파는 기존 내비게이션과 뚜렷이 다른 SoleMap을 시범 도입했습니다. 내비게이션이 차로 단위로 가장 빠른 길을 알려 준다는 소문이 퍼지면서, 직선나라의 모든 내비게이션이 SoleMap으로 바뀌었습니다. 자차 이용자가 갑자기 늘어 도로가 무너지지 않을지 걱정한 키파는 현대오토에버에 ‘도로 부담’이라는 값을 계산하도록 지시했습니다.

키파는 대통령이 되기 전에 수학과 공학을 깊이 공부했기 때문에, 실무자가 애써 지표를 만들지 않아도 되도록 도로 부담을 엄밀하게 정의해 두었습니다. 각 도로에 대해 도로 부담은, 매일 그 도로를 이용하는 차량 수를 $c$대라 할 때, $c$대의 차량을 $w$개의 차로가 적절히 나누어 지나도록 했을 때 각 차로를 지나는 차량 대수의 제곱의 합으로서 가능한 최솟값입니다.

예를 들어 어떤 도로에 대해 $c=4$, $w=3$이라면, 차로는 차량을 다음과 같이 나눌 수 있습니다.

• 한 차로에 $4$대가 모두 다니는 경우, $4^{2}+0^{2}+0^{2}=16$
• 한 차로에 $3$대, 다른 차로에 나머지 $1$대가 다니는 경우, $3^{2}+1^{2}+0^{2}=10$
• 한 차로에 $2$대, 다른 차로에 나머지 $2$대가 다니는 경우, $2^{2}+2^{2}+0^{2}=8$
• 한 차로에 $2$대, 다른 차로에 $1$대, 나머지 차로에 마지막 $1$대가 다니는 경우, $2^{2}+1^{2}+1^{2}=6$

이 중 최솟값인 $6$이 도로 부담입니다.

SoleMap의 프로그래머인 당신이 직선나라의 교통 상황을 받아 각 도로의 도로 부담을 계산해 승진의 기회를 노려 봅시다!

첫 줄에 도시의 수 $N$과 차량 정보의 개수 $M$이 공백으로 구분되어 주어집니다. ($2\leq N\leq 500\,000$; $1\leq M\leq 500\,000$)

둘째 줄에 $(N-1)$개의 정수 $w_{1}$, $w_{2}$, $\cdots$, $w_{N-1}$이 공백으로 구분되어 주어집니다. ($1\leq w_{i}\leq 10^{9}$) 이는 각 $1\leq i\leq(N-1)$에 대해 $i$번 도시와 $(i+1)$번 도시를 잇는 도로가 $w_{i}$차로라는 뜻입니다.

다음 $M$개의 줄에 교통 상황이 주어집니다. 각 $1\leq j\leq M$에 대해 $(j+2)$번째 줄에 $u_{j}$, $v_{j}$, $x_{j}$가 공백으로 구분되어 주어집니다. ($1\leq u_{j}<v_{j}\leq N$; $1\leq x_{j}\leq 10^{9}$) 이는 매일 $u_{j}$번 도시에서 $v_{j}$번 도시로 가는 차량이 $x_{j}$대 있다는 뜻입니다.

주어지는 모든 $x_{j}$의 합은 $10^{9}$을 넘지 않습니다.

$(N-1)$개의 줄을 출력합니다.

각 $1\leq i\leq(N-1)$에 대해 $i$번째 줄에 $i$번 도시와 $(i+1)$번 도시를 잇는 도로의 도로 부담을 출력합니다.

다음과 같이 매일 도로를 이용하는 차량 수를 계산할 수 있습니다.

• 1번 도시와 2번 도시를 잇는 도로: $3+0=3$대
• 2번 도시와 3번 도시를 잇는 도로: $3+1=4$대
• 3번 도시와 4번 도시를 잇는 도로: $0+1=1$대

다음과 같이 각 도로의 도로 부담을 계산할 수 있습니다.

• 1번 도시와 2번 도시를 잇는 도로의 도로 부담: 차선이 하나밖에 없으므로 $3^{2}=9$
• 2번 도시와 3번 도시를 잇는 도로의 도로 부담: 앞서 설명한 대로 $6$
• 3번 도시와 4번 도시를 잇는 도로의 도로 부담: 차가 한 대밖에 없으므로, 어느 차선으로 달리든 $1^{2}+0^{2}+0^{2}+0^{2}=1$