题目描述

农夫FJ和奶牛Bessie在玩单词游戏。Bessie脑海里总共有n个单词，而且有m个记忆关联，每个记忆关联的格式是：x、y、t，表示当Bessie记得单词x时，只需要t微秒就能记起单词y。FJ和Bessie总共玩q轮游戏，每轮游戏开始时FJ都会给出两个单词u和v，表示：假如Bessie一开始记得单词u，那么Bessie至少需要多少微秒才能记起单词v？请输出对应答案。每轮游戏相互独立，互不影响。

输入格式

第一行输入两个整数 $n$ 和 $m$，满足 $2 \le n \le 1000$，$1 \le m \le 1000$。 接下来 $m$ 行，每行输入三个元素：单词 $x$、单词 $y$、整数 $t$。其中 $x$、$y$ 均由小写字母构成且长度不超过 20，$t \le 1000$。单词 $x$ 和 $y$ 之间可能存在多个记忆关联。 接下来一行输入一个整数 $q$，满足 $1 \le q \le 1000$。 最后 $q$ 行，每行输入两个单词 $u$ 和 $v$。

输出格式

输出共 $q$ 行，每行对应一轮游戏的答案。若Bessie无法从单词 $u$ 记起单词 $v$，则输出 $-1$。

输入输出样例

输入样例1

3 2
novak goat 1
goat simulator 3
2
novak simulator
simulator goat

输出样例1

4
-1