즐거운 길

집으로 걸어갈 때 나는 항상 가장 짧은 길로 가는 것이 아니라, a) 항상 집에 더 가까워지고, b) 지나온 길 구간의 "즐거움 계수" 평균이 최대가 되는, 즉 "가장 즐거운" 길로 간다. 그러한 평균의 최댓값을 계산하는 프로그램을 작성하라.

내 도시의 지도는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 장소로 나타낼 수 있다. 장소 $1$은 나의 출발지이고 장소 $n$은 나의 집이며, 장소들은 거리순으로 정렬되어 있어 번호가 큰 장소가 번호가 작은 장소보다 항상 집에 더 가깝다.

또한 $m$개의 서로 다른 "길 구간"이 있고, 각 구간은 어떤 장소 $u\_i$에서 다른 장소 $v\_i$로 이어지며 즐거움 계수 $w\_i$를 가진다. 이 계수는 특이한 나무나 창가에 앉은 귀여운 고양이 등 즐거운 무언가 때문일 수 있다. 나는 항상 집 방향으로 걷고 싶으므로, 설명에는 $u\_i<v\_i$인 길 구간만 포함되어 있다.

수학에 조금 관심 있는 사람이라면(이 자리에 그런 사람이 있다면) 이것을 방향이 있고 가중치가 있는 비순환 그래프라고 부를 수 있을 것이다.

두 번째 예제의 지도. 가장 즐거운 길은 $1\rightarrow 3\rightarrow 5$이다.

첫째 줄에는 두 정수 $n$과 $m$이 주어진다 ($2 \leq n \leq 10^5$ , $1 \leq m \leq 2\cdot 10^5$). 다음 $m$개의 줄은 각각 하나의 길 구간을 나타내며 세 정수 $u\_i$, $v\_i$, $w\_i$를 포함한다 ($1 \leq u\_i < v\_i \leq n$, $1 \le w\_i \le 2\cdot 10^6$). 이는 길 구간이 장소 $u\_i$에서 장소 $v\_i$로 이어지고 즐거움 계수가 $w\_i$임을 뜻한다.

같은 두 장소를 잇는 길 구간은 둘 이상 존재하지 않으며, 장소 $1$에서 장소 $n$으로 갈 수 있음이 보장된다.

장소 1에서 장소 $n$으로 가는 길에서 얻을 수 있는 즐거움 계수 평균의 최댓값을 한 수로 출력하라. 상대 오차 또는 절대 오차가 $10^{-6}$ 이하이면 정답으로 인정된다.