题目描述

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

输入格式

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

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

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

输出格式

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

样例

输入样例

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

数据范围与提示

1≤​n​≤200

1≤​k​≤n2

1≤​m​≤20000

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