길을 잃은 놀이공원
시간 제한1초메모리 제한512 MB
연결된 가중치 그래프에서 사이클이 최대 하나일 때, 시작 정점을 균등하게 고르고 같은 정점을 다시 방문하지 않는 무작위 경로의 길이 기댓값을 구합니다.
문제
여름 방학이 되었지만 어린 Z는 집에서 너무 심심했다. 그래서 혼자 놀이공원에 가기로 했다. 입구에 들어선 Z는 지도를 살펴보았다. 놀이공원 전체는 n개의 명소와 이들을 잇는 m개의 통로로 이루어진 연결된 무방향 그래프로 나타낼 수 있었다. 또한 그래프에는 사이클이 최대 하나만 있다(따라서 m은 n 또는 n − 1이다). Z의 현재 위치인 입구도 명소 중 하나이다.
Z는 어떤 명소가 재미있는지 모르므로, 현재 위치에서 출발해 이후 매 단계마다 현재 명소와 통로로 연결된 다른 명소로 이동하기로 했다. 같은 명소(입구 명소 포함)는 두 번 방문하지 않는다. 놀기 좋아하는 Z는 현재 있는 명소와 그 인접 명소를 모두 방문할 때까지 계속 논다.
Z가 방문하는 명소의 순서는 단순 경로가 된다. Z는 이 경로의 기대 길이를 알고 싶어 한다.
Z는 지도를 집에 가져왔지만 입구가 어느 명소인지는 잊어버렸다. 어떤 명소든 입구일 확률이 같다고 가정한다. 또한 다음에 방문할 명소를 고를 때마다, 인접한 미방문 명소는 모두 같은 확률로 선택된다.
입력
첫 줄에 명소의 수 n과 통로의 수 m이 주어진다.
이어지는 m개의 줄에는 정수 Xi, Yi, Wi가 주어진다. 이는 i번째 통로가 명소 Xi와 Yi를 잇고 길이가 Wi임을 뜻한다. 명소는 1부터 n까지 번호가 매겨져 있다. 두 명소를 잇는 통로는 최대 하나이다.
출력
경로의 기대 길이를 나타내는 실수 하나를 한 줄에 출력한다. 절대 오차 또는 상대 오차가 0.0001 이하이면 정답으로 인정한다.
제한
3 ≤ m ≤ n ≤ 100000
그래프의 모든 단순 사이클은 최대 20개의 정점을 포함한다.