### 问题描述 *LOST GRACE DISCOVERED* 史东薇尔城坐落于宁姆格福与利耶尼亚湖的交界处，地势险要、易守难攻，是连接南北重要的交通枢纽。史东薇尔城不仅地理位置重要，内部更是错综复杂，第一次来到这里的褪色者往往会迷路。魔法师 MaverickFW 接手了大量的来自史东薇尔城的任务委托，每一次执行任务 MaverickFW 都需要从自己当前的所在地去往史东薇尔城再跑去任务地点。我们将地图简化为一张无向图，而史东薇尔城是 $1$ 号结点。 MaverickFW 想知道自己每次任务最短需要跑多远，他每次会告诉你自己当前所在结点与任务地所在结点，希望你能准确回答他。 ### 输入格式 输入第 $1$ 行包含两个正整数 $n$ 和 $m$，分别表示节点数和边数。 接下来 $m$ 行每行包含三个正整数 $v_i,w_i,d_i$ ，表示 $v_i$ 到 $w_i$ 的距离为 $d_i$。 接下来 $1$ 行包含一个整数 $T$，表示询问次数。 最后 $T$ 行，每行包含两个正整数 $s_i,t_i$，表示 MaverickFW 的出发点与任务点。 ### 输出格式 对于每一个询问输出一行，这一行只包含一个整数，表示答案。 ### 样例输入 ``` 3 3 1 2 1 1 3 1 2 3 1 3 1 3 2 3 1 2 ``` ### 样例输出 ``` 1 2 1 ``` ### 说明/提示 对于所有评测数据，$n\in[2,10^5]，m\in[n−1,\frac{n\times (n−1)}2]，1\leq v_i,w_i\leq n，d_i\in[0,10^5]，T\in[1,10^5]，1\leq s_i,t_i\leq n$。