대동여지도

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

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

세종이는 두 지역을 연결할 수 있는 도로를 모두 설치하고 싶지만 국고가 부족하다. 그래서 최소한의 비용으로 모든 지역을 이동할 수 있도록 도로를 설치하려 한다. 최소 비용을 만드는 방법이 여러 가지라면 우선순위가 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$개의 지역을 연결하기 위해 도로를 설치할 때 필요한 최소 비용을 출력한다.

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

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

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