【题目描述】

工厂为了生产一种复杂的产品，给各个生产部门制定了详细的生产计划。那么，就经常会有生产部门要把产品送到另一个生产部门作为原料。这是一个注重产品质量的工厂，所以每当有产品要从 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 6
1 2 3
1 3 5
4 1 7
5 4 1
5 3 1
5 3 2
3
4 2
5 3
2 3

【样例输出】

10
13
-1

【数据规模与约定】

30%的数据，n≤100，m≤500，w=1

60%的数据，n≤100，m≤5000

另 20%的数据，q=1

100%的数据，2≤n≤3000，m≤100000，2≤a,b≤n， q≤100000，1≤u,v≤n，1≤w≤10000

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

工厂的员工都非常尽职尽责，他们的认真和热情决定了产品的完美，所以不必考虑产品不合格的情况。在质量检验处的检验时间也忽略不计。