基站
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

在牛牛世界中,作为强者的你发现了这个牛牛世界的一个很奇妙的性质。

这个世界是由 n个点,m条边 ( x , y , z ) 组成的一个无向图。

这个图上有k个点是基站,两基站 ( x , y ) 之间的距离是这样定义的:

从x出发的时候有一个能量d,每走一条权值为z的边,能量就会衰减z,走到任意一个基站会恢复成能量d,整个过程需要保证d>=0,一直走到y
其中满足条件的最小的d就是距离,如果不存在这样的d,那么距离就为0.现在只有求出基站之间的距离的最大值,你才会开心

输入描述:

n,m

m条边m行,每行x,y,z表示x到y有一条权值为z的边

k基站数量,同一行输入k个数表示k个基站

输出描述:

一个整数,答案


示例1

输入

复制
6 9
1 2 2
2 3 5
3 4 7
4 5 11
5 1 12
3 5 9
2 4 4
2 6 11
2 3 5
3 1 4 6

输出

复制
13

说明

1到6的距离为13,没有其他距离13更大

备注:

对于40%的测试数据:1 <= n <= 1000

对于100%的测试数据: 2 <= k <= n <= 100000, 1 <= m <= 500000 , 1 <= x,y <= n , 1 <= z <= 10000