흐름을 따라서

세상은 정점 $N+1$개로 이루어져 있고, 각 정점에는 $0$번부터 $N$번까지 번호가 붙어 있다. 정점 사이에는 간선이 놓여 있는데, 모든 간선은 일방통행이고 간선마다 지나가는 데 걸리는 시간이 다르다. 동현이는 지금 $0$번 정점에 있고, $N$번 정점이 동현이의 집이다.

동현이는 집에 도착하기 전까지 마음이 가는 대로 세상을 떠돈다. 마음이 가는 대로 움직인다는 것은 현재 정점에서 나가는 간선을 모두 같은 확률로 하나 고른 뒤 그 간선을 따라 다음 정점으로 간다는 뜻이다. 같은 두 정점을 잇는 간선이 여러 개 있으면 각각을 서로 다른 간선으로 센다. 자기 자신으로 돌아오는 간선도 있을 수 있다. $N$번 정점에 도착하면 그 자리에서 멈춘다.

$0$번 정점에서 출발해 집에 도착할 때까지 걸리는 시간의 기댓값을 구하라.

예를 들어 세상이 아래 그림과 같다고 하자.

$0$번 정점에서 동현이는 각각 $1/2$ 확률로 시간 $1$을 써서 $1$번 정점으로 가거나, 시간 $1$을 써서 $2$번 정점으로 가 집에 도착한다. $1$번 정점에서도 각각 $1/2$ 확률로 시간 $2$를 써서 $0$번 정점으로 돌아오거나, 시간 $2$를 써서 집에 도착한다. 이 경우 답은 아래와 같다.

$\frac{1}{2}\times 1+\left(\frac{1}{2}\right)^{2}\times(1+2)+\left(\frac{1}{2}\right)^{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 \le N,\ 1 \le t \le 50)$가 공백으로 구분되어 주어진다. $x$번 정점에서 $y$번 정점으로 가는 간선이 있고 그 간선을 지나는 데 시간이 $t$만큼 걸린다는 뜻이다. 모든 정점에서 $N$번 정점으로 가는 경로가 존재하도록 간선이 주어진다. 따라서 $0$번부터 $N-1$번까지의 정점에는 나가는 간선이 적어도 하나 있다.

$0$번 정점에서 출발해 집인 $N$번 정점에 도착할 때까지 걸리는 시간의 기댓값을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 값이 정수여도 소수점 아래 여섯 자리를 모두 적는다. 답은 $10^{6}$을 넘지 않으며, 소수점 아래 여섯째 자리에서의 반올림이 애매해지는 입력은 주어지지 않는다.