시간은 곧 돈이다

한 통신 회사가 $N$개의 마을에 초고속 인터넷을 제공하려고 합니다. 이를 위해서는 어느 마을에서 출발하든 다른 모든 마을로 메시지가 전달될 수 있도록, 마을 사이를 잇는 초고속 회선 $N-1$개로 이루어진 네트워크를 건설하면 충분합니다.

직접 연결이 가능한 모든 마을 쌍은 이미 파악되어 있으며, 연결 가능한 각 회선마다 건설에 드는 비용과 건설에 걸리는 시간을 알고 있습니다.

회사는 전체 네트워크를 건설하는 데 드는 총 시간(회선은 한 번에 하나씩 건설하므로 시간이 더해집니다)과 총 비용을 모두 최소화하고 싶어 합니다. 두 기준 중 하나를 고를 수 없어, 다음과 같이 네트워크의 값을 평가하기로 했습니다.

• $\text{SumTime}$ = 선택한 회선들의 건설 시간의 합
• $\text{SumMoney}$ = 선택한 회선들의 건설 비용의 합
• $V = \text{SumTime} \times \text{SumMoney}$

값 $V$가 최소가 되도록 건설할 회선 $N-1$개를 선택하세요.

첫째 줄에 두 정수 $N$(마을의 수)과 $M$(직접 연결이 가능한 마을 쌍의 수)이 주어집니다. 마을은 $0$부터 $N-1$까지 번호가 매겨져 있습니다.

다음 $M$개의 줄에는 각각 네 정수 $x$, $y$, $t$, $c$가 주어집니다. 이는 마을 $x$와 마을 $y$를 건설 시간 $t$, 비용 $c$로 연결할 수 있음을 뜻합니다.

주어진 회선들만으로 모든 마을을 서로 연결할 수 있음이 보장됩니다.

가능한 값 $V = \text{SumTime} \times \text{SumMoney}$ 중 최솟값을 정수 하나로 출력하세요.

• $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$을 만족합니다.