Daedong Yeojido Roads

Sejong is looking at Daedong Yeojido, a map from the Joseon era. He wonders how much it would cost to build roads that connect every region, including Hanyang.

Three kinds of roads can be built: walking-only roads, horse-only roads, and carriage-only roads.

Sejong wants to build every road that can connect two regions, but the royal treasury is short on funds. He will build roads so that every region can be reached from every other region at the minimum total cost. If several sets of roads reach that minimum cost, he picks the set with the most first-priority roads. If that still ties, he picks the set with the most second-priority roads.

Help Sejong find the minimum cost, and report how many roads of each type are built along with their total cost.

The first line has the number of places $N$ and the number of roads $M$. $(2 \le N \le 10\,000$, $N-1 \le M \le 200\,000)$

The second line has three different road types $p_i$ in priority order, highest first. Each value is $0$ for walking-only, $1$ for horse-only, or $2$ for carriage-only. $(0 \le p_i \le 2)$

Each of the next $M$ lines has four values $u_i$, $v_i$, $w_i$, $k_i$. $u_i$ and $v_i$ are place numbers. $(u_i \ne v_i$, $1 \le u_i, v_i \le N)$. $w_i$ is the cost to build the road. $(1 \le w_i \le 10\,000)$. $k_i$ is the road type, where $0$ is walking, $1$ is horse, and $2$ is carriage. $(0 \le k_i \le 2)$

The input guarantees that all places can be connected.

On the first line, print the minimum cost to connect all $N$ places.

On the second line, print the number of walking-only roads built and their total cost, separated by a space.

On the third line, print the number of horse-only roads built and their total cost, separated by a space.

On the fourth line, print the number of carriage-only roads built and their total cost, separated by a space.