7626: 道路重建

【问题描述】
　　从前有个王国，王国有N个城市，M条道路。两个城市之间最多只有一条道路。战争过后，有D条道路被摧毁了。国王想重建道路，使得最重要的两个城市A和B互通。
　　你的工作就是决定重建哪些道路能使得AB相连并且重建的道路的长度总和最少。

【输入格式】
　　有多组测试数据。
　　每组测试数据的第一行为一个整数N（2 < N≤100），表示城市的数目。城市的编号为1、2、3…N。
　　第二行为一个整数M(N-1≤M≤N*(N-1)/2),表示道路的数目。
　　下来M行，每行三个整数I，J，K（1≤I,J≤N,I≠J,0 < K≤100）,表示I和J之间有直接的道路长度为K。
　　下来一行为一个整数D（1≤D≤M），表示被摧毁的道路的数目。
　　下来D行每行两个整数I，J，表示城市I和J之间的道路被摧毁。
　　最后一行为两个整数A和B。表示两个重要的城市。
　　输入当N=0时结束，并且不做任何处理。

【输出格式】
　　每组测试数据输出一行，输出重建道路的长度的总和的最小值。

Input

3
2
1 2 1
2 3 2
1
1 2
1 3
0

Output

1

3 
2 
1 2 1 
2 3 2 
1 
1 2 
1 3 
0 

1