[{"sectionTitle":"题目描述","type":"Text","text":"原题来自：HNOI 2009\r\n\r\n考虑带权的有向图 $G=(V,E)$ 以及 $w:E\\to R$，每条边 $e=(i,j)(i\\not =j,i\\in V,j\\in V)$ 的权值定义为 $w_{i,j}$，令 $n=|V|$。$c=(c_1,c_2,\\cdots ,c_k)(c_i\\in V)$ 是 $G$ 中的一个圈当且仅当 $(c_i,c_{i+1})(1\\le i\\lt k)$ 和 $(c_k,c_1)$ 都在 $E$ 中，这时称 $k$ 为圈 $c$ 的长度。同时令 $c_{k+1}=c_1$，并定义圈 $c=(c_1,c_2,\\cdots ,c_k)$ 的平均值为：\r\n\r\n$$\mu (c)=\frac{1}{k}\sum_{i=1}^k w_{c_i,c_{i+1}}$$\r\n\r\n即 $c$ 上所有边的权值的平均值。\r\n\r\n令 $\\mu^*(c)=\\min \\{\\mu (c)\\}$ 为 $G$ 中所有圈 $c$ 的平均值的最小值。现在的目标是：在给定了一个图 $G=(V,E)$ 以及 $w:E\\to R$ 之后，请求出 $G$ 中所有圈 $c$ 的平均值的最小值 $\\mu ^* (c)=\\min \\{ \\mu (c)\\}$。","subType":"markdown"},{"sectionTitle":"输入格式","type":"Text","text":"第一行包含两个正整数 $n$ 和 $m$，并用一个空格隔开，其中 $n=|V|,m=|E|$，分别表示图中有 $n$ 个顶点和 $m$ 条边；\r\n\r\n接下来 $m$ 行，每行包含用空格隔开的三个数 $i,j,w_{i,j}$，表示有一条边 $(i,j)$ 且该边的权值为 $w_{i,j}$。\r\n\r\n输入数据保证图 $G=(V,E)$ 连通，存在圈且有一个点能到达其他所有点。","subType":"markdown"},{"sectionTitle":"输出格式","type":"Text","text":"仅包含一个实数 $\\mu ^*=\\min \\{ \\mu (c) \\}$，要求输出到小数点后 $8$ 位。","subType":"markdown"},{"sectionTitle":"样例 1","type":"Sample","text":"","subType":"markdown","payload":["4 5\n1 2 5\n2 3 5\n3 1 5\n2 4 3\n4 1 3","3.66666667"]},{"sectionTitle":"样例 2","type":"Sample","text":"","subType":"markdown","payload":["2 2\n1 2 -2.9\n2 1 -3.1","-3.00000000"]},{"sectionTitle":"数据范围与提示","type":"Text","text":"对于 $20\\%$ 的数据，$1\\le n\\le 100,1\\le m\\le 1000$； \r\n对于 $40\\%$ 的数据，$1\\le n\\le 1000,1\\le m\\le 5000$； \r\n对于 $100\\%$ 的数据，$1\\le n\\le 3000,1\\le m\\le 10^4,|w_{i,j}|\\le 10^7$。\r\n\r\n输入保证 $1\\le i,j\\le n$。","subType":"markdown"}]