题目描述

画一个$n$个节点，$m$ 条边的带权有向图，想从中找出权值的平均值最小的环。有向图中可能不存在环，求最小的平均权值。

输入

共 $m+1$ 行。 第$1$行，$2$个整数$n$和$m$，表示点数和边数。 第$2\sim m+1$行，每行$3$个正整数 $u，v，w$，表示$u$与$v$之间有一条权值为$w$的有向边。

输出

如果输入数据无环，输出“PaPaFish is laying egg!”。（不含引号） 否则输出一个浮点数 $ans$，表示所有环中，权值的平均值最小的环的平均权值。答案保留$2$位小数。

输入样例

2 2
1 2 2
2 1 3

输出样例

2.50

提示

【数据规模】 对于前40%的数据 $n≤50，m≤5000$； 对于100%的数据 $1≤n≤1000，1≤m≤10000，0≤w≤10000000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。