#1641. 寻宝游戏

寻宝游戏

题目描述

有一张 nn 个点 mm 条边的带正整数边权无向连通图,图上有 zz 个关键点。

你可以选择一条从一个关键点到另一个关键点的简单路径,设这条路径上边权和为 ww,那么你的得分将会是 ww 个服从 [0,1][0, 1] 上的连续型均匀分布的互相独立的随机变量中第 kk 小的期望值。

请选择这样一条路径,最大化最后的得分。请将得分对 3152519739159347331525197391593473 取模后输出。

输入格式

第一行三个整数,n,m,kn, m, k

接下来mm行每行三个整数 u,v,cu, v, c,表示 uuvv 间有一条边权为 cc 的边(保证 ckc\ge k)。

接下来一行一个整数 zz

接下来一行 zz 个整数,表示关键点的编号。

输出格式

一行一个数,答案。

样例

6 5 1
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
3
3 4 1
15762598695796737

数据范围与提示

对于所有数据,2zn105,2\le z\le n\le 10^5, m5×105,m\le 5\times 10^{5}, 1kc1091\le k\le c\le 10^9

子任务编号 分值 特殊性质
1 30 n,m1000n, m\le 1000
2 10 给定的图是一条链
3 20 给定的图是一棵树
4 40