N개의 도시 간에 통신망을 설치하려고 합니다.

우선 설치할 수 있는 통신망들의 목록을 추려놓았고, 그 개수는 M개입니다. 각 통신망은 두 도시간의 통신을 가능하게 하며, 쓸데없이 통신망을 설치하는 경우를 없애기 위해서 통신망이 N개 도시의 신장트리가 되도록 설치하려고 합니다.

신장트리라는 말은, N개의 도시에 대해 임의의 두 도시를 고르면, 두 도시가 다른 도시를 통해 서로 통신할 수 있으며, 통신을 하기 위해 거쳐야 하는 도시의 경로가 하나 뿐인, 즉 트리의 형태를 이루고 있어야 한다는 말입니다.

그러나 각 통신망은 효용성도 다르고, 유지비도 다릅니다. 신장 트리를 만들게 되면 통신망을 N-1개 만들어야 하는데, 이때 각 통신망의 효용성을 g_i, 유지비를 c_i라고 했을 때,

을 최대화하여 신장 트리를 만드는 프로그램을 작성하세요.

입력

• 첫 번째 줄에는 도시의 개수 N(1≤N≤1,000)과 설치 할 수 있는 통신망 후보의 개수 M(1≤M≤10,000)이 주어집니다.
• 다음 M줄에 걸쳐 통신망후보의 정보가 입력되는데, 각 줄마다 각 통신망이 연결하는 도시의 번호 x, y(각 도시는 0에서 N-1사이의 정수로 표시된다.)와 그 통신망의 효용성 g와 유지비 c가 주어집니다. g와 c는 모두 100이하의 자연수입니다. 신장트리를 만들지 못하는 경우는 주어지지 않습니다.

출력

입출력 예

입력

3 3
0 1 8 5
1 2 4 4
2 0 7 3

출력

1.87500

예제 설명

• 0과 1을 연결하는 통신망과 1과 2를 연결하는 통신망을 선택하는 경우 -> 1.33333
• 1과 2를 연결하는 통신망과 2와 0을 연결하는 통신망을 선택하는 경우 -> 1.57143
• 2와 0을 연결하는 통신망과 0과 1을 연결하는 통신망을 선택하는 경우 -> 1.87500

출처:august14