不可思议的迷宫
题目背景
融合了强力的装备,当然要去探索迷宫了
题目描述
然而,在你用一套神装愉快的切瓜切菜时,慧音大小姐对你发动了忘却技能,于是,没有融合"记"印记的你忘记了迷宫的构造。
由于在忘却前你对这个迷宫的构造已经了如指掌,所以你知道这个迷宫的 $ n $ 个房间都是互相连通的,并且有 $ n $ 条道路连接这些房间(当然,道路从两个方向都可以经过)
即使在不可思议的幻想乡,基本的常识也是存在的,也就是说不会有连接两个相同房间的道路,也不会有两端是同一个房间的道路。
忘记了迷宫的构造后,你无从得知你在哪里,以及前往下一层的通道在哪里.幸运的是,你保存了一份这个迷宫大致的地图,知道了这 $ n $ 条道路分别连接哪两个房间以及每条道路的长度。
为了通关,你会从你所在的位置(某个随机的位置)不重复经过道路地走向前往下一层的通道(某个随机的位置),显然,这种路径可能不止 $1$ 条,那么这时你会随机选取其中一条。
现在,你想知道自己走过的路径的期望长度,为了避免精度误差,只要对 $19260817$ 取模就好了。
输入输出格式
输入格式
第一行一个整数 $n$,表示房间以及道路的个数。
下面 $n$ 行每行三个整数 $u,v,w$,表示从房间 $u$ 到房间 $v$ 有一条长度为 $w$ 的道路。
输出格式
一行一个整数,表示期望路径长度。
输入输出样例
输入样例 #1
4
1 4 2
4 2 2
3 4 2
2 3 2
输出样例 #1
8426611
说明
#### 样例解释:
迷宫的结构如下:
![](https://cdn.luogu.com.cn/upload/pic/42707.png)
起始点和结束点都是随机的,用二元组$(x,y)$表示
以几个有代表性的二元组为例:
$(1,1)$,只有一条长度为$0$的路径
$(1,2)$,有两条路径$1-4-2,1-4-3-2$,期望路径长度为 $\frac{4+6}{2}=5$
$(3,3)$,有两条路径$3-2-4,3$,期望路径长度为 $\frac{6+0}{2}=3$
不难算出,将所有可能的二元组的期望路径长度加在一起为$57$,所以答案为 $\frac{57}{16}$ ,在模意义下等于 $8426611$。
#### 数据范围:
![](https://cdn.luogu.com.cn/upload/pic/42697.png)