32114번 - SoleMap

문제

현대오토에버 로고

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

처음 가는 길을 운전할 때, 갈림길을 잘못 들거나 차선을 잘못 타서 곤란해하는 사람을 지켜본 경험이 누구나 한 번쯤은 있을 겁니다. 내비게이션이 있어도 초행길은 내비게이션 화면과 실제 도로를 머릿속에서 바로 대입하기 어려운 경우가 많습니다. 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이 되었습니다. 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$