폭염 코스 구역

문제

마라톤 대회 조직위원회는 N개의 체크포인트(1번부터 N번)와 이들 사이에 놓을 수 있는 M개의 후보 구간을 가지고 있다. 후보 구간은 양방향이고 길이가 양의 정수이다. 양 끝이 같은 체크포인트인 구간이 있을 수도 있고, 같은 두 체크포인트 사이에 여러 구간이 있을 수도 있다. 폭염 대응 규칙에 따라 그날의 허용 길이 X가 정해지면 길이가 X 이하인 구간만 코스로 쓸 수 있다. 쓸 수 있는 구간만 따라 서로 오갈 수 있는 체크포인트들은 하나의 구역을 이룬다. 구간이 하나도 닿지 않는 체크포인트도 그 하나만으로 하나의 구역이다. 위원회는 각 구역 안의 모든 체크포인트가 서로 연결되도록 쓸 수 있는 구간 중 일부를 골라 코스로 확정하되, 고른 구간의 길이 합이 최소가 되게 한다. 즉 쓸 수 있는 구간으로 이루어진 그래프의 최소 신장 숲을 만든다. Q개의 허용 길이 X가 주어질 때, 각각에 대해 구역의 수, 최소 신장 숲에 쓰인 구간의 길이 총합, 가장 큰 구역에 속한 체크포인트의 수를 구하시오. 각 질문은 서로 독립이며, 길이가 같은 구간이 여럿이어도 총합은 하나로 정해진다.

입력

첫 줄에 N, M, Q 가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 20000, 0 ≤ M ≤ 14000, 1 ≤ Q ≤ 10000 이다. 이어서 M개의 줄에 구간의 양 끝 체크포인트 번호 u, v (1 ≤ u, v ≤ N)와 길이 w (1 ≤ w ≤ 10^6)가 주어진다. 이어서 Q개의 줄에 허용 길이 X (0 ≤ X ≤ 10^6)가 하나씩 주어진다. 모든 값은 정수이다.

출력

각 질문마다 한 줄에 '구역의 수', '길이 총합', '가장 큰 구역의 크기'를 공백으로 구분하여 질문 순서대로 출력한다.

5 5 4
1 2 3
2 3 5
1 3 4
4 5 2
3 4 9
1
3
8
10

5 0 1
3 5 2
2 9 3
1 18 5

1 0 2
0
5

1 0 1
1 0 1

3 3 2
1 1 1
1 2 7
1 2 7
7
6

2 7 2
3 0 1

출처: Devin.KR 자체 제작