题目描述

工厂为了生产一种复杂的产品，给各个生产部门制定了详细的生产计划。那么，就经常会有生产部门要把产品送到另一个生产部门作为原料。这是一个注重产品质量的工厂，所以每当有产品要从A部门运到B部门时，都要先从A部门送到质量检验处，检验合格后再从质量检验处运到B部门。 有些部门之间有传送带连接，厂长想知道每次将产品从一个部门运送到另一个部门最少需要多长时间。

输入格式

第一行两个整数 $n,m$，$n$ 表示部门数量，$m$ 表示传送带数量。出于方便，$1$ 号部门是质量检验处。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示有一条从 $u$ 部门到 $v$部门的传送带，传送过去需要 $w$ 个单位时间。注意传送带是单向的。

接下来一个整数 $q$，表示有 $q$ 次运送。

接下来 $q$ 行，每行两个数 $a,b$，表示这一次要将产品从 $a$ 部门运送到 $b$ 部门。

输出格式

输出 $q$ 行，每行一个整数，表示这次运送最少需要的时间。若没有传送方案，输出 -1。

5 5
1 2 3
1 3 5
4 1 7
5 4 1
5 3 1
3
4 2
5 3
2 3

10
13
-1

数据范围

$2≤n≤3000$

$1 \le m≤10^5$

$2≤a,b≤n$

$1 \le q≤10^5$

$1≤u,v≤n$

$u \neq v$

$1≤w≤10000$

有些部门之间可能有多条传送带。