32339번 - 대동여지도

문제

세종이는 조선 시대의 지도인 대동여지도를 보면서 한양을 포함한 모든 지역을 연결하는 도로를 설치한다면 비용이 얼마나 들지 궁금해졌다.

설치할 수 있는 도로의 종류는 총 3가지로 도보 전용 도로, 말 전용 도로, 마차 전용 도로가 있다.

세종이는 지역을 연결할 수 있는 모든 도로를 전부 설치하고 싶지만 국고가 부족한 관계로 최소한의 비용을 사용하여 모든 지역을 이동할 수 있도록 도로를 설치하려 한다. 만약 최소한의 비용으로 도로를 설치할 수 있는 경우가 여러가지라면, 조정에서 지정해준 우선순위가 1번째인 도로가 가장 많은 순으로, 이 경우도 여러가지라면 우선순위가 2번째인 도로가 가장 많은 순으로 설치하려 한다.

세종이를 도와 최소한의 비용을 사용하여 모든 지역을 연결하는 도로를 설치하고, 설치에 드는 총 비용과 도보, 말, 마차 전용 도로 각각의 설치 개수와 비용을 파악해보자.

입력

첫 번째 줄에 장소의 개수 $N$과 설치할 수 있는 도로의 개수 $M$이 주어진다. $(2 \le N \le 10,000円;$ $N-1 \le M \le 200,000円)$

두 번째 줄에 서로 다른 도로 종류 $p_i$가 우선순위가 높은 순서대로 3개 주어지며, 각각 0ドル$은 도보 전용 도로, 1ドル$은 말 전용 도로, 2ドル$는 마차 전용 도로를 의미한다. $(0 \le p_i \le 2)$

다음 $M$개의 줄에 걸쳐 두 장소를 연결하는 경로의 정보 $u_i,ドル $v_i,ドル $w_i,ドル $k_i$가 주어진다.

$u_i,ドル $v_i$는 각각 지역 번호를 의미한다. $(u_i \ne v_i;$ 1ドル \le u_i, v_i \le N)$

$w_i$는 도로의 설치 비용을 의미한다. $(1 \le w_i \le 10,000)$

$k_i$는 도로의 종류를 의미하며, 각각 0ドル$은 도보 전용 도로, 1ドル$은 말 전용 도로, 2ドル$는 마차 전용 도로를 의미한다. $(0 \le k_i \le 2)$

입력은 모든 지역을 연결할 수 있도록 주어진다.

출력

첫 번째 줄에 $N$개의 지역이 연결하기 위해 도로를 설치할 때 필요한 최소 비용을 출력한다.

두 번째 줄에 최소 비용으로 도로를 설치할 때 도보 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

세 번째 줄에 최소 비용으로 도로를 설치할 때 말 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

네 번째 줄에 최소 비용으로 도로를 설치할 때 마차 전용 도로의 설치 개수와 비용을 공백으로 구분하여 출력한다.

제한

힌트