题目描述

给定一个有向图，图里有 $n$ 个点。$m$ 条单向边，给定 $q$ 次查询 a b，每次查询求解从 $a$ 号点到 $b$ 号点的最短距离；

输入格式

第一行包含三个整数 $n, m, q；$

接下来 $m$ 行每行包含三个整数 $a, b, c$ 表示存在一条从 $a$ 点 到 $b$ 点 且长度为 $c$ 的一条单向边；

接下来 $q$ 行，每行包含两个整数 $a, b$ 表示询问点从 $a$ 点 到 $b$ 点 的最短距离；

输出格式

共 $q$ 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible；

数据范围

$1 \leq n \leq 300.$

$1 \leq m \leq 10000.$

$1 \leq q \leq 100000.$

$-100000 \leq c \leq 100000.$

输入样例：

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

输出样例：

1
1
impossible