28296번 - 물류창고

UCPC시에는 $N$개의 물류창고가 있으며, $K$개의 회사가 각 물류창고를 소유하고 있다. 물류창고에는 $1$번부터 $N$번까지 차례대로 번호가 붙어있으며, 회사 또한 $1$번부터 $K$번까지 차례대로 번호가 붙어있다. $M$개의 양방향 도로가 두 물류창고를 연결하고 있으며, 도로마다 물건의 이동 상한선이 정해져 있다. 두 물류창고 사이에는 여러 개의 도로가 있을 수 있으며, 임의의 두 물류창고를 연결하는 경로는 언제나 존재한다.

두 물류창고 사이에서 물건을 배송한다고 생각해 보자. 두 물류창고를 연결하는 경로상의 도로 중 가장 작은 이동 상한선이 두 물류창고의 배송 상한선이 된다. 만약 두 물류창고를 연결하는 경로가 여러 개 존재한다면, 그중에서 배송 상한선이 가장 큰 경로를 선택할 것이다.

각 회사에 대해, 해당 회사에 속한 물류창고끼리의 배송 상한선들의 총합을 구해보자.

단, 각 회사는 $2$개 이상의 물류창고를 소유하고 있음이 보장된다.

첫 번째 줄에 물류창고의 수 $N$, 회사의 수 $K$, 도로의 수 $M$이 공백으로 구분되어 주어진다. $(2\leq N\leq 100\ 000;\ 1\leq K\leq\min(\frac{N}{2} ,50\ 000) ;\ N-1\leq M\leq 300\ 000)$

두 번째 줄에는 $N$개의 정수 $C_1,\ C_2,\ ...,\ C_N$ 가 공백으로 구분되어 주어지며, 이는 $i$번 물류창고를 $C_i$번 회사가 소유함을 나타낸다. $(1\leq C_i\leq K)$

이후 $M$개의 줄에 걸쳐 도로들의 정보가 주어진다. 각 줄에는 세 개의 정수 $X$, $Y$, $W$가 공백으로 구분되어 주어지며, 이는 $X$번 물류창고와 $Y$번 물류창고를 연결하는 이동 상한선 $W$의 양방향 도로를 나타낸다. $(1\leq X,Y\leq N;\ 1\leq W\leq 10^9)$

총 $K$개 줄에 걸쳐 $1$번 회사부터 $K$번 회사까지 각 회사에 속한 물류창고끼리의 배송 상한선들의 총합을 출력한다.