영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
When I go home, I don't always choose the shortest path, but rather a path that
- always takes me closer to my home, and
- is ”nicest”, in the sense that the average ”niceness factor” of the path segments I pass is as high as possible.
Write a program that computes the maximum such average.
The map of my city can be described by n places numbered from 1 to n. Place 1 is where I start, and place n is my home. All places are sorted by the distance to my home, so a place with a higher number is always closer to my home than one with a lower number.
Furthermore, there are m different path segments that each lead from one place u_i to another place v_i and has a niceness factor of w_i. The niceness factor could depend on for example whether the path segment contains some rare trees, a cute cat sitting in a window or some other nice thing. Since I always want to go home, the description only includes path segments where u_i < v_i.
If you are mathematically inclined, we might call this a directed, weighted, acyclic graph.
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The map in the second example. The nicest path is 1 → 3 → 5.
Input
The first line consists of the integers n and m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 2 · 10^5), the number of places and the number of path segments.
Each of the following m lines describe a path segment and consists of the three integers u_i, v_i and w_i (1 ≤ u_i < v_i ≤ n, 1 ≤ w_i ≤ 2 · 10^6), which means that a path segment goes from place u_i to place v_i with a niceness factor of w_i.
There will never be more than one path segment connecting two places, and it's guaranteed that it's possible to get from place 1 to place n.
Output
Output a single number: the highest possible average niceness factor on a path from place 1 to place n. Your answer will be considered correct if its relative or absolute error is at most 10^-6.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
| 1 | 21 | 2 ≤ n ≤ 10, 1 ≤ m ≤ 20 |
| 2 | 41 | 2 ≤ n ≤ 1000, 1 ≤ m ≤ 2000 |
| 3 | 38 | No additional constraints. |
예제
예제 1
3 3 1 2 20 2 3 17 1 3 18
18.5000000000
예제 2
5 6 1 2 20 2 3 17 1 3 18 4 5 19 3 5 23 2 4 22
20.5000000000