那是遥远的公元前2333年，V8还有女朋友的时代。

他和他的女友分别是两个距离遥远的部落的首领，那时候没有现在发达的交通工具和路网，V8每次希望团圆的时候，都要跋山涉水不远万里去会见他的爱人，辛酸的很。经过很多次的旅途，V8掌握了他可以走的所有的路的路线图，毕竟作为首领，不能离开自己的领地太久，所以V8希望你给他找出一条最近的路，并且输出一次往返所需要的最短时间，V8并不会在对方领地停留，说个你好就回来了，需要的时间为0。

虽然不管你求出来有多快，最终V8还是觉得自己在路上花费的时间太多，选择了舍小家而为大家（手动滑稽。

第一行一个正整数t，表示数据的组数（t <=10）。

之后对于每组数据，第一行一个正整数k，表示这个地图（无向图）的路径数（k<=10000）。

之后有k行，每一行三个正整数，s，t，v。表示路的两个端点和这条路需要的时间（s,t,v <=100）。

第k+1行为两个数，v,m，表示V8和他爱人的所在地。

对于每组数据，输出一行一个正整数，为V8一个来回最短的时间（数据保证有通路）。