题目描述

给定一个 n 个点 m 条边的有向图，图中不存在自环、负环，可能有重边以及负权边 。 现在有q次查询，每次查询需要回答x->y的最短路，请你进行程序设计。

输入格式

第一行包含整数 n , m, q。 接下来 m 行每行包含三个整数 u, v, w，表示存在一条从点 u 到点 v 的有向边，边长为 w。 接下来 q 行每行有两个整数x, y, 表示查询x->y的最短路。

输出格式

输q行， 每行对应每次查询的最短路结果， 若无法到达输出impossible。

4 3 2
1 2 5
2 3 -3
1 3 4
1 3
1 4

2
impossible

数据规模与约定

$1≤ n ≤ 200，1 ≤ m≤ 10^4, 1 ≤ q ≤ 5\times 10^3$ 边长绝对值均不超过 100。