题目描述

Farmer John经营着一片大型农场。农场上有\(n\)个大棚，编号为\(1 \sim n\)。某些大棚之间可能有道路直接相连，共计\(m\)条道路，每条道路都有一定的修建成本。奶牛们对Farmer John的管理极其不满，于是它们对农场进行了大破坏。
痛定思痛，Farmer John下定决心要努力维护好农场。但在此之前，他要把被奶牛破坏的道路重新修建好。有\(d\)条道路被奶牛破坏，重修道路的成本与最初修建时相同，未被破坏的道路则无需重修。修复过程中不会新建原来没有的道路。
由于工程量巨大，短时间内修完\(d\)条道路有些不太现实，所以Farmer John想要先让最重要的两个大棚A和B之间有道路直接或间接相连。请计算：至少需要投入多少修建成本，才能满足A与B相连？如果无论怎样修路都不能使A与B相连，输出-1。

输入格式

每个输入文件含有多组测试数据。对于每组测试数据：
第一行是两个正整数：\(n\)和\(m\)；
之后\(m\)行，每行3个正整数\(u,v,c (u < v)\)，表示大棚\(u\)与大棚\(v\)直接有道路直接相连，该道路的修建成本为\(c\)。输入时保证不会出现重边；
之后一行是一个正整数\(d\)；
之后\(d\)行，每行两个正整数\(u,v (u < v)\)，表示大棚\(u\)与大棚\(v\)之间的道路被奶牛破坏了。输入时保证每条被破坏的道路都是原来就有的，且同一条路在该部分输入中不会出现多次；
最后一行是两个正整数\(A,B\)，表示最重要的两个大棚的编号。
文件的末尾为两个0，表示输入结束。

输出格式

每行一个整数。对于每组测试数据，依次输出答案。

样例

输入

4 4
1 2 5
1 3 4
2 4 7
3 4 8
2
1 2
3 4
1 4
0 0

输出

5

数据范围及约定

20%的数据满足：\(n \le 20\)
40%的数据满足：\(n \le 200\)
60%的数据满足：\(n \le 2000\)
100%的数据满足：\(n \le 10000, \quad m \le 50000\)