멋진 경로

나는 집에 갈 때 항상 최단 경로를 선택하지 않고, 다음 조건을 만족하는 경로를 선택한다.

• 항상 집에 더 가까워지며,

• 지나가는 경로 구간들의 평균 ''쾌적도''가 가능한 한 높다는 의미에서 ''가장 멋진'' 경로이다.

이러한 평균의 최댓값을 계산하는 프로그램을 작성하라.

내 도시의 지도는 $1$부터 $n$까지 번호가 매겨진 $n$개의 장소로 나타낼 수 있다. 장소 $1$은 출발지이고, 장소 $n$은 내 집이다. 모든 장소는 집까지의 거리를 기준으로 정렬되어 있으므로, 번호가 더 큰 장소는 번호가 더 작은 장소보다 항상 집에 더 가깝다.

또한, 서로 다른 $m$개의 경로 구간이 있으며, 각 경로 구간은 장소 $u_i$에서 다른 장소 $v_i$로 이어지고 쾌적도는 $w_i$이다. 쾌적도는 예를 들어 경로 구간에 희귀한 나무가 있는지, 창가에 귀여운 고양이가 앉아 있는지, 또는 그 밖의 멋진 것이 있는지에 따라 달라질 수 있다. 나는 항상 집으로 가고 싶어 하므로, 설명에는 $u_i < v_i$인 경로 구간만 포함된다.

수학적인 표현을 선호한다면, 이를 방향성 가중 비순환 그래프라고 부를 수 있다.

두 번째 예제의 지도. 가장 멋진 경로는 $1\rightarrow 3\rightarrow 5$이다.

점수

여러 테스트 그룹으로 해답을 테스트하며, 각 그룹에는 정해진 점수가 있다. 한 테스트 그룹의 점수를 받으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

$1$ |$21$| $2 \le n \le 10$, $1 \le m \le 20$

$2$ |$41$| $2 \le n \le 1000$, $1 \le m \le 2000$

$3$ |$38$| 추가 제한 없음.

첫째 줄에 장소의 수와 경로 구간의 수를 나타내는 정수 $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$). 이는 쾌적도가 $w_i$인 경로 구간이 장소 $u_i$에서 장소 $v_i$로 이어진다는 뜻이다.

두 장소를 연결하는 경로 구간은 하나보다 많지 않으며, 장소 $1$에서 장소 $n$까지 갈 수 있음이 보장된다.

장소 $1$에서 장소 $n$까지 가는 경로에서 가능한 평균 쾌적도의 최댓값을 하나의 수로 출력한다. 답의 상대 오차 또는 절대 오차가 최대 $10^{-6}$이면 정답으로 인정된다.