该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Farmer John 有 N 个农场，编号为 1 ~ N。

有 M 条单向通行的道路。通过每条道路需要花费一定的时间。有些道路的通行时间为负，说明这些道路是虫洞，通过这些道路可以时光倒流。

至少有一个农场，从该农场出发可以到达其他所有的农场。

奶牛 Bessie 想要找一条环形跑路线，使得路线上除了起点外，中途不能重复经过同一个农场。

Bessie 希望经过每条边的平均时间尽可能短，你能帮助她吗？

输入格式

第一行：两个整数 N 和 M

接下来的 M 行：每行三个数 a, b, c，表示从农场 a 到农场 b 有一条单向道路，通行时间为 c

输出格式

经过每条边的最短平均时间，保留 8 位小数。如果无解，则输出 No solution

样例输入1

4 5
1 2 3
2 3 3
3 1 3
2 4 2
4 1 1

样例输出1

2.00000000

样例输入2

2 2
1 2 -2.3
2 1 -2.7

样例输出2

-2.50000000

样例输入3

3 2
1 2 -2.3
1 3 -2.7

样例输出3

No solution

数据范围

100%的数据：$N ≤ 5×10^3, M ≤ 10^5,|c| ≤ 10^7$