C1912 [Contest #14]飞翔的小鸟

一日，小鸟想要进行旅行。

旅程图由 $n$ 个景点与 $m$ 条有向通道组成，景点和通道皆由 $1$ 开始编号。第 $i$ 条通道起点为第 $x_i$ 个景点，终点为第 $y_i$ 个景点，并且有个高度参数 $h_i$，表示此条通道的缺口高度，当且仅当小鸟在此高度时能够通过这条通道。

在每个景点会有休息的位置，小鸟可以在此任意调节自己的高度。

小鸟非常地喜欢刺激的旅程，他想让自己通过的通道的最大高度与最小高度的差最大。即使到达了终点，也不一定要立即结束旅行，小鸟仍可以再去其他景点后再绕回来。

有 $q$ 次询问，第 $i$ 次询问会给你一个景点编号 $t_i$，请输出以 $1$ 号景点为起点， $t_i$ 为终点时，小鸟旅行中走过的路线中最大高度与最小高度差的最大值，若不存在经过的通道数目大于 $0$ 的路线，输出 -1。

样例输入 1

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

样例输出 1

5
3
5

样例输入 2

3 1 3
1 2 1
3
2
1

样例输出 2

-1
0
-1

样例输入 3

2 3 1
1 2 1
2 1 1
1 2 2
2

样例输出 3

1

样例输入 4

10 15 6
1 2 8
2 3 8
3 4 6
4 5 7
5 6 7
6 7 7
7 8 9
8 9 10
9 10 5
5 2 6
1 7 7
8 6 8
9 10 10
9 8 8
4 2 6
3
2
4
7
1
10

样例输出 4

2
2
2
4
-1
5