小doge的快乐阳光跑

题号：NC53247
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

nit是小w所在的学校，我们认为该学校可以近似成一个由n个点和m条无向边组成的连通图。

nit的体育分数里有一项是阳光跑。

每次开始阳光跑，会在n个点里随机生成好多点位，并且需要按照点位顺序跑。

假设学校的结构如上图所示，本次阳光跑随机生成了5个点位分别为3,1,2,4,3。

那么如果想要完成阳光跑，就必须从某个点出发，然后按照给出顺序依次经过3->1->2->4->3。

当然，阳光跑只要求你对于这些点位按照顺序经过，实际上你在跑到一半的时候也可以拐去其他的位置。

在上述的例子中，假设你按照3->4->2->1->2->4->3这个顺序进行跑步，也可以完成3,1,2,4,3这五个点位。

也就是说当且仅当，阳光跑随机生成的点位序列（注意顺序）是你跑步序列的一个子序列时，你完成阳光跑。

某一个序列的子序列指的是，保留该序列的顺序并删除一些元素或者不进行删除后的结果。

小doge是一个乐于助人的好孩子，他常常帮助别人跑步。

这天，小doge想要完成自己的阳光跑并且顺便帮助小w一起完成即一个人完成两人的任务，并且两个人的任务是独立的，小doge有a个点位，小w有b个点位。小doge想要最效率的跑法，所以他想知道他最少要跑多远。小doge可以选择任何一个点出发。

对于阳光跑的要求，我们如下定义：有n个有顺序的点位 $a_1$ ~ $a_n$ ，想要完成阳光跑，必须按照顺序依次经过每个点位，并且在到达前一个点位后到达下一个点位才有效。

ps: 这是违规操作，小朋友们不要模仿。

输入描述:

第一行输入n,m。
下面m行，每行输入x,y,v。代表一条无向边以及该边的距离。
接着输入两行，接下来一行输入的第一个整数a，表示小doge的点位数量，并且在该行后面跟着输入a个整数，按照顺序给出小doge的点位。 接下来再一行输入的第一个整数b，表示小w的点位数量，并且在该行后面跟着输入b个整数，按照顺序给出小w的点位。

输出描述:

仅一行一个整数，表示完成跑步的最短路程。

示例1

输入

复制

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

输出

复制

说明


第一个人没有点位，相当于只有一个人进行阳光跑。
然后最优的跑步方案是3->1->2->4->3，包含子序列3,1,2,4,3符合题意，并且跑步距离为11

示例2

输入

复制

输出

复制

说明


然后最优的跑步方案是3->1->2->5->4->3。
这个方案既包含了子序列3,1,4,3。
有包含了子序列3,2,5。
注意：两个人的跑步任务互不影响，所以在3号点开始时，同时完成了两个人的点位。即这两个子序列可以包含公共部分。

备注:


当a或者b为0时，可视作阳光跑序列为空，我们认为空序列是任何序列的子序列。