No submission language available for this problem.

Background

Special for beginners, ^_^

Description

给定一个 n 个顶点 m 个边的有向图，图中不存在重边和自环，边的权重都是整数。 再给定 k 次查询，每次查询包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短路径的距离。 如果路径不存在，则输出 impossible，如果存在，则输出最短路径的距离。

Format

Input

第一行包含三个整数 n,m,k。

接下来 m 行每行包含三个整数 x, y, z，表示存在一条从点 x 到点 y 的有向边，边的权重为 z。

接下来 k 行，每行对应依次询问，包含两个整数 a, b，表示询问从顶点 a 到顶点 b 的最短路径距离。

Output

共 k 行，每行输出一个整数，表示这次询问的结果，如果两点间存在最短路径，则输出最短路径的距离，如果不存在，则输出 impossible。

Samples

6 3 8
3 5 8
3 4 24
4 3 22
6 2
5 3
4 2
1 6
5 3
5 2
3 5
2 4

impossible
impossible
impossible
impossible
impossible
impossible
8
impossible

Limitation

$1≤n≤200$

$1≤k≤n^2$

$1≤m≤20000$

图中的每条边的权重值不大于 50

1s, 1024KiB for each test case.