문제

정점 개, 간선 개의 무향 가중치 연결 그래프 가 입력된다.

집합 는 를 만족하는 모든 를 원소로 가지고 있다.

집합 에서 한 원소 를 무작위로 골라 에 정점 와 를 연결하는 가중치 의 간선을 추가로 연결한 그래프 를 만들었을 때 의 MST(Minimum Spanning Tree)의 가중치의 합의 기댓값을 구하여라.

입력

첫째 줄에 과 이 주어진다.

그 다음 개 줄에 정점 와 를 가중치 로 연결하는 간선을 의미하는 간선정보 가 주어진다.

출력

첫째 줄에 무작위로 간선을 추가했을 때 MST의 가중치 합의 기댓값을 으로 나눈 나머지를 출력한다.

노트

그래프의 모든 정점들을 포함하는 연결된 부분 그래프 중에서 간선의 가중치의 합이 최소인 것을 MST(Minimum Spanning Tree)라고 한다.

유리수를 기약분수로 나타냈을 때

인 경우, 이 수를 소수인 로 나눈 나머지는 을 만족하는 이상 미만의 정수 이며, 가 의 배수가 아닌 경우 이 값은 유일하다.

은 소수이다.