U437514 五秒真男人

这个“五秒真男人”是指祢衡，这是“[八秒真男人](https://www.luogu.com.cn/problem/U370453)”

噔噔蹬蹬噔噔蹬蹬瞪瞪（鼓声） 当祢衡击鼓骂曹后，曹操便让他(ノ｀Д)ノ出使荆州。 荆州的刘表看他桀骜不驯，于是便让他巡视周边。 祢衡很高兴，结果到了之后才发现，这~~TM的~~也太远了！ 祢衡很不爽，恰巧他的朋友——你——蒯良很聪明，于是祢衡就寻求你的帮助，你顺利的帮他找到了最短路。 后来，刘表又双叒叕的派他出使。 祢衡很烦，于是问你：“你有办法吗？” damn，你心想，汤姆的刘表烦不烦。 你的兄弟蒯越于是给出了一份代码，祢衡很高兴，但他拿不准这个代码对不对，于是就请教你对不对。 （注：祢衡要从x地点出发，巡视到1地点，再去y地点报告， 你需要给出最短路，然后祢衡再用蒯越的代码调一遍，代码如下： ``` #include using namespace std; int main(){ printf("我为什么要告诉你（这句话是对做题的人说的）"); } ``` ）

第一行一个整数T,n,m，表示有T次巡视，n个点，m条边。 接下来m行每行三个整数a,b,s,表示第a地区与第b地区有距离为s的路（无向，但是因为某种超自然因素，聪明的作者为你提供了自环） 接下来T行，每行两个整数x,y，问它们的最短路。

T行输出结果，用换行隔开。

数据保证有路。 1≤T≤25000 2×T≤N≤50000 1≤M≤100000 1