给一个 个点 条边的连通无向图，满足每条边最多属于一个环，有 组询问，每次询问两点之间的最短路径。
输入的第一行包含三个整数，分别表示 和 和 。
下接 行，每行三个整数 ，表示一条无向边 ，长度为 。
最后 行，每行两个整数 ，表示一组询问。
输出 行，每行一个整数表示询问的答案。
9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7
5 6
对于 的数据，，。
