题目描述

给你一张简单有向图，边权都为非负整数。以及一些询问，询问两个点之间的距离。

图用以下形式给出：

第一行输入三个整数 $n,m,k$，表示图的顶点数、边数和询问次数，顶点编号从 1 到 $n$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 到 $y$ 有一条有向边，边权为 $z$。

接下来 $k$ 行，每行两个整数 $x,y$，询问从 $x$ 到 $y$ 的最短路长度，如果无法到达，输出 -1。

输入格式

第一行三个整数 $n,m,k$，表示图的顶点数、边数和询问次数。

接下来 $m$ 行，每行有三个整数，代表一条边。

接下来 $k$ 行，每行有两个整数，代表一次询问。

输出格式

输出共 $k$ 行，每行一个数表示一次询问的答案。

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

5
-1

数据规模

对于所有数据，保证 $2≤n≤5000,0≤m≤10000,1≤k≤10,1≤x,y≤n,x≠y,1≤z≤10000$。