道路重建

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 rebuild.in 输出文件 rebuild.out

【问题描述】

有一次，在一个王国中，有N个城市。N条道路可以让你从一个城市到其他任何一个城市。在两个城市之间最多有1条道路，但在一次严酷的战争后，有D条路被破坏。国王想要修理这些路，A和B是两个重要的城市，国王想要让两个城市尽快的连接，现在你的工作就是重建道路使A和B连接且重建道路的总长度最少。
【输入格式】
输入文件第一行包括一个整数N（2<N≤100）表明城市数。这些城市编号为从1到N。第二行包括一个整数M（N-1≤M≤N*（N-1）/2），表明道路的数量。下面有M行，每行有3个整数I,J,K（1≤I，J≤N，I≠J，0<K≤100）,意思是城市I与城市J之间道路的长度为K。
下一行包括一个整数D（1≤D≤M），表示有几条路被破坏。下面D行包括2个整数I,J，表示城市I与城市J之间的道路被破坏且可以直接连接。
最后一行有两个整数A和B，表示两个重要的城市。
【输出格式】

   对于每组测试数据，输出只有一行是可以使A和B连接的重建道路的总长度。

【输入样例】
输入文件名：rebuild.in
3
2
1 2 1
2 3 2
1
1 2
1 3
 
输出文件名：rebuild.out
1