C. 最短路径

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

平安夜那天,小 Y 要在公益集市上买一些东西。

公益集市因为人太多了,小 Y 不会去挤,所以他会发动技能在某两个摊位间瞬移(双向),然而瞬移需要花费一定能量。

现在公益集市有 个摊位, 号点是小 Y 的宿舍, 号点是机房,小 Y 会从宿舍出发,最后到机房。小 Y 只会在 个摊位买东西,但是在买某个摊位的东西之前,小叶子可能要先买某个摊位的东西。即对于每一个限制条件 ,小 Y 只有在买完 的东西之后才可以买 的东西。这些限制只存在于那 个摊位间。当然,小 Y 在任何时候可以到达某个摊位而不买东西。总之,小 Y 在到达机房的时候一定要按照符合的规定在这 个摊位都买过东西。

现在请你帮小 Y 算出他最少需要花费的能量。

输入格式

第一行输入三个整数 表示总点数和边数,和小 Y 要买东西的摊位数。(这些摊位是 号点)

接下来 行,每行三个整数 表示 和 点之间小 Y 花费 点能量可以互相到达。

接下来一个整数 , 表示有 组给定的顺序。

接下来 行,每行两个整数 , 表示小 Y 买 号摊位的东西之前要买 号摊位的东西。

输出格式

一个整数 , 表示最少需要花费的能量。

样例

样例输入

8 15 4
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5

样例输出

19

样例解释

。

数据范围与提示

对于 的数据,;

对于 的数据,;

对于 的数据,, , , , .

保证运算过程中数据范围在 int 以内。