The CS nerd is very desperate to find the girl.

After air-dropping thousands of papers with cardioid equations, the CS nerd has gained enough confidence to approach the girl at school and possibly talk about some Thanksgiving Feast. However, he has no idea where in the school building she is. The CS nerd can't let his courage drop! Thus, he begins a desperate search to find the girl.

The school that the CS nerd is at has $N$ common meeting areas (numbered $1$ to $N$) and $M$ bi-directional hallways. Each hallway is in the form of $u$ $v$ $w$. $u$ and $v$ signify the two meeting areas that the hallway connects and $w$ is the time required to take the hallway. It is guaranteed that any meeting area is reachable from any other meeting area.

The CS nerd starts at meeting area $1$, while the girl could be in any single meeting area in the school with equal probability (including meeting area $1$; in this case, the CS nerd finds her in $0$ time), but she does not move. When the CS nerd reaches a meeting area without the girl, he will randomly choose a hallway to take. Each hallway connected to the current meeting area has an equal probability of being chosen. If the CS nerd reaches a meeting area with the girl, he stops searching.

What is the expected time, in seconds, that the CS nerd will take searching for the girl? In other words, if the CS nerd simulates his searching infinite times, what is the average time it takes for him to find the girl?

Constraints

For all subtasks:

The largest time cost of a hallway is $100$.

Subtask 1 [10%]

$N=2$

$1\le M\le 25$

Subtask 2 [30%]

$N=3$

$1\le M\le 1000$

Subtask 3 [20%]

$2\le N\le 50$

$1\le M\le 10000$

Subtask 4 [40%]

$2\le N\le 300$

$1\le M\le 100000$

Input Specification

The first line will contain two space-separated integers, $N$ and $M$.

The next $M$ lines are in the form of three space-separated integers $u$, $v$, $w$, $u\ne v$, signifying a hallway between meeting areas $u$ and $v$ with a time cost of $w$.

Output Specification

On a single line, output the expected time, in seconds, that the CS nerd will take searching for the girl. Your answer will be judged as correct if it has an absolute or relative error no greater than ${10}^{-6}$.

Sample Input 1

2 2
1 2 5
1 2 3

Sample Output 1

2.000000

Explanation for Sample Output 1

If the girl is located at meeting area 1, the CS nerd spends $0$ seconds searching for her. If the girl is located at meeting area 2, the CS nerd has a 50% chance of taking the hallway with a time cost of 3 and another 50% chance of taking the hallway with a time cost of 5. Thus, the expected time of making it to meeting area 2 is $0.5\cdot 3+0.5\cdot 5=4$ seconds. In total, the expected time is $0.5\cdot 0+0.5\cdot 4=2$ seconds.

Sample Input 2

3 2
1 2 60
1 3 60

Sample Output 2

120.000000

Sample Input 3

5 5
1 2 1
1 3 1
1 4 1
3 4 1
4 5 1

Sample Output 3

5.733333