{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"随着新版百度空间的上线,Blog 宠物绿豆蛙完成了它的使命,去寻找它新的归宿。"}},{"title":"Description","value":{"format":"MD","content":"给出张 $n$ 个点 $m$ 条边的有向无环图,起点为 $1$,终点为 $n$,每条边都有一个长度,并且从起点出发能够到达所有的点,所有的点也都能够到达终点。\n\n绿豆蛙从起点出发,走向终点。 到达每一个顶点时,如果该节点有 $k$ 条出边,绿豆蛙可以选择任意一条边离开该点,并且走向每条边的概率为 $\\frac{1}{k}$ 。现在绿豆蛙想知道,从起点走到终点的所经过的路径总长度期望是多少?"}},{"title":"Input","value":{"format":"MD","content":"输入的第一行是两个整数,分别代表图的点数 $n$ 和边数 $m$。\n\n第 $2$ 到第 $(m + 1)$ 行,每行有三个整数 $u, v, w$,代表存在一条从 $u$ 指向 $v$ 长度为 $w$ 的有向边。"}},{"title":"Output","value":{"format":"MD","content":"输出一行一个实数代表答案,四舍五入保留两位小数。"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4 \n1 2 1 \n1 3 2 \n2 3 3 \n3 4 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7.00\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"MD","content":"#### 数据规模与约定\n\n- 对于 $20\\%$ 的数据,保证 $n \\leq 10^2$。\n- 对于 $40\\%$ 的数据,保证 $n \\leq 10^3$。\n- 对于 $60\\%$ 的数据,保证 $n \\leq 10^4$。\n- 对于 $100\\%$ 的数据,保证 $1 \\leq n \\leq 10^5$,$1 \\leq m \\leq 2 \\times n$,$1 \\leq u, v \\leq n$,$1 \\leq w \\leq 10^9$,给出的图无重边和自环。"}}]}