시간이 돈 Batch Compilation commands

승현이가 운영하는 정보통신 회사 aintelecom은 $N$개의 도시에 인터넷을 보급하고자 합니다. 이를 위해서는 두 도시를 연결하는 통신선 $N-1$개를 지어 모든 도시가 통신선을 통해 연결되도록 하면 됩니다. 빠른 정보력을 자랑하는 aintelecom은 이미 통신선을 지을 수 있는 도시의 쌍들을 모두 알아냈으며, 각 후보 쌍마다 통신선을 구축하는 데 드는 비용과 시간도 알아냈습니다.

aintelecom은 위 조건을 만족하도록 통신선을 가능한 한 적은 비용과 시간을 들여 구축하고 싶어합니다. ()그러나 어느 것이 중요한지 가늠할 수 없었으므로, 아래 공식을 통해 이를 짓는 데 드는

SumTime = 선택한 각 후보에 대해 통신선을 구축하는 데 걸리는 시간의 합
SumMoney = 선택한 각 후보에 대해 통신선을 구축하는 데 걸리는 비용의 합
V = SumTime * SumMoney

해야 할 일

V의 값을 최소화하도록 지어야 할 N-1개의 통신선을 찾는 프로그램을 작성하세요.

입력 형식

첫 번째 줄에 도시의 수 $N$과 연결될 수 있는 도시의 쌍의 수 $M$이 주어집니다. 도시들은 $0$부터 $N-1$까지의 번호가 붙어 있습니다. 다음 $M$개 줄에는 네 개의 정수 $x, y, t, c$가 주어집니다. 이는 $x$번 도시와 $y$번 도시 사이에 통신선을 지을 수 있으며, 짓는다면 $t$만큼의 시간과 $c$만큼의 비용이 든다는 의미입니다.

출력 형식

첫 번째 줄에 V를 최소화하도록 통신선을 구축하는 데 드는 총 시간과 비용을 공백을 사이로 두고 출력합니다. 다음 $N-1$개 줄에는 통신선으로 연결해야 할 두 도시의 번호 $x$와 $y$를 공백을 사이로 두고 출력합니다. 이 때, 두 도시 $x$와 $y$는 입력에서 연결 가능하다고 주어져 있어야 합니다. 출력 순서는 임의로 결정해도 좋습니다. 최적의 답안이 여러 개 존재할 경우, 아무거나 출력하면 됩니다.

제약 조건

• $1 \le N \le 200.$
• $1 \le M \le 10,000.$
• $0 \le x, y \le N-1.$
• $1 \le t,c \le 255.$
• 데이터 하나는 $M = N - 1.$
• 40%의 데이터는, 모든 후보 통신선에 대해 t = c.

입출력 예제

예제 1

입력

5 7
0 1 161 79
0 2 161 15
0 3 13 153
1 4 142 183
2 4 236 80
3 4 40 241
2 1 65 92

출력

279 501
2 1
0 3
0 2
3 4