题目描述

有一张 $n$ 个点 $m$ 条边的带正整数边权无向连通图，图上有 $z$ 个关键点。

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

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

输入格式

第一行三个整数，$n, m, k$。

接下来$m$行每行三个整数 $u, v, c$，表示 $u$ 和 $v$ 间有一条边权为 $c$ 的边（保证 $c\ge k$）。

接下来一行一个整数 $z$。

接下来一行 $z$ 个整数，表示关键点的编号。

输出格式

一行一个数，答案。

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

15762598695796737

数据范围与提示

对于所有数据，$2\le z\le n\le 10^5,$ $m\le 5\times 10^{5},$ $1\le k\le c\le 10^9$。