Following Flow Batch Compilation commands

세상은 $N + 1$개의 정점으로 이루어져 있는데, 각 정점은 $0$에서 $N$까지의 번호가 붙어있다. 각 정점에서는 다른 정점으로 가는 간선이 있는데, 각 간선은 일방통행이며, 각 간선마다 간선을 지나가는데 걸리는 시간이 다르다. 동현이는 세상을 떠돌고 있는데, $0$번 지점은 동현이가 현재 있는 위치이고, $N$번은 동현이의 집이다. 동현이는 집에 도착하기 전까지는 마음이 가는 대로 세상을 떠돌고 싶어한다. 마음이 가는 대로라는 것은 현재 정점에서 다른 정점으로 갈 수 있는 모든 간선에 대해 동일한 확률로 한 간선을 선택하여 다음 정점으로 가는 것이다. 이 때 동현이는 집으로 가기까지 걸리는 시간의 기댓값이 어느 정도 일지 궁금하다. 예를 들어 세상이 다음과 같이 이루어져 있다고 생각해보자.

다음과 같은 경우 처음에 동현이는 $0$번 지점에서 각각 $50%$의 확률로 $1$초가 걸려 $1$번 지점으로 이동하거나 $1$초가 걸려 $2$번 지점으로 이동하여 집에 도착하게 된다. $1$번 지점으로 가는 경우 역시 $50%$의 확률로 $3$초가 걸려 $0$번 지점으로 돌아오거나 $3$초가 걸려 $2$번 지점으로 이동하여 집에 도착하게 된다. 이 경우 답은 아래와 같다.

$\frac{1}{2} \times 1 + (\frac{1}{2})^2 \times (1+2) + (\frac{1}{2})^3 \times (1+2+1) + \cdots = \frac{8}{3}$

입력 형식

첫 번째 줄에는 정점의 개수를 나타내는 $N$ $(1 \le N \le 30)$과 간선의 개수를 나타내는 $M$ $(1 \le M \le 1,000)$이 공백으로 구분되어 주어진다. (실제 정점 개수는 $N + 1$임에 주의하라)

다음 $M$개의 줄에는 각 줄마다 $x, y, t$ $(0 \le x < N, 0 \le y < N, 1 \le t \le 50)$가 공백으로 구분되어 주어지는데, $x$에서 $y$로 가는 간선이 있고 가는데 시간이 $t$만큼 걸린다는 뜻이다. 어떤 정점에서든 정점 $N$으로 가는 길이 있도록 간선이 주어진다.

출력 형식

정점 $0$에서 출발하여 집 (정점 $N$) 에 도착할 때까지 걸리는 시간의 기댓값을 출력하라. 답과의 절대 혹은 상대 오차가 $10^{-6}$ 이하라면 정답으로 인정된다. 답은 $10^{6}$ 을 넘지 않음이 보장된다.

입력

2 4
0 1 1
1 0 2
0 2 1
1 2 2

출력

2.666666667