물류창고
시간 제한2초메모리 제한1024 MB
도로로 연결된 창고 그래프에서 회사별로 소유한 창고 쌍의 최대 병목 운송 한도를 구하고, 그 합을 회사마다 출력합니다.
문제
UCPC시에는 개의 물류창고가 있고, 개의 회사가 각 물류창고를 소유하고 있다. 물류창고에는 번부터 번까지, 회사에는 번부터 번까지 차례대로 번호가 붙어 있다. 개의 양방향 도로가 두 물류창고를 잇고 있으며, 도로마다 물건의 이동 상한선이 정해져 있다. 두 물류창고 사이에 도로가 여러 개 있을 수 있으며, 임의의 두 물류창고를 잇는 경로는 항상 존재한다.
두 물류창고 사이에서 물건을 배송한다고 하자. 두 물류창고를 잇는 경로에 있는 도로들 중 이동 상한선이 가장 작은 값이 두 물류창고의 배송 상한선이 된다. 두 물류창고를 잇는 경로가 여러 개라면, 그중 배송 상한선이 가장 큰 경로를 고른다.
각 회사에 대해, 그 회사에 속한 물류창고끼리의 배송 상한선을 모두 더한 값을 구한다.
단, 각 회사는 물류창고를 2개 이상 소유하고 있음이 보장된다.
입력
첫 번째 줄에 물류창고의 수 , 회사의 수 , 도로의 수 이 공백으로 구분되어 주어진다.
두 번째 줄에는 개의 정수 이 공백으로 구분되어 주어진다. 번 물류창고는 번 회사가 소유한다.
이후 개의 줄에 도로 정보가 주어진다. 각 줄에는 정수 , , 가 공백으로 구분되어 주어지며, 이는 번 물류창고와 번 물류창고를 잇는 이동 상한선 의 양방향 도로를 뜻한다.
출력
총 개 줄에 걸쳐 번 회사부터 번 회사까지, 각 회사에 속한 물류창고끼리의 배송 상한선 총합을 한 줄에 하나씩 출력한다.