eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Drunken Walk

Drunken Walk

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

After having a bit too much to drink in the evening, you find yourself going on a long walk on a directed graph—but not too long, as there are no cycles. You start at vertex 0, and whenever you are at a vertex, you will randomly leave the vertex along one of its outgoing edges with probability proportional to the weight of the edge.

You continue walking until you reach a vertex that has no edges leaving it, after which you fall asleep. The length of your walk is the number of edges you traverse. Moreover, before leaving vertex 0, you may choose one edge from anywhere in the graph that you do not like and ignore it during your walk (or you may choose to not ignore any of them). Determine the longest possible expected length of your walk.

Входные данные

The input consists of multiple test cases. Each test case begins with a line containing two integers N, 2N10000, and M, 1M100000, the number of vertices and edges in the graph, respectively. The next M lines each contain three integers u, v, and w (1w1000), indicating that there is a directed edge from vertex u to vertex v (numbered from 0 to N−1) with weight w. The input terminates with a line with N = M = 0.

Выходные данные

For each test case, print out a single line that contains the longest possible expected length of your walk. Your answer will be considered correct if it is within 10^{−6} absolute or relative precision.

Пример

Входные данные #1
4 5
0 1 2
0 2 1
0 3 3
1 3 1
2 3 4
9 8
0 1 1
1 2 1
2 3 1
0 4 2
4 5 10
4 6 1
6 7 1
7 8 1
0 0
Выходные данные #1
2.00000000
3.66666667
Источник 2011 Stanford Local ACM Programming Contest, Saturday, October 8th, 2011