该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

Format

Input

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

Output

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

Sample 1

Input

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

Output

5

Limitation

1s, 131072KiB for each test case.

Hint

对于20%的数据满足：n≤20
对于40%的数据满足：n≤200
对于60%的数据满足：n≤2000
对于100%的数据满足：n≤10000，m≤50000

Source

tywz