You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1672 题。

题目描述

有 $n$ 个城市和 $m$ 条航班连接它们。你的任务是处理 $q$ 个查询，每个查询要求你确定两个给定城市之间的最短路径长度。

输入格式

第一行包含三个整数 $n$, $m$ 和 $q$：分别表示城市的数量、道路的数量和查询的数量。

接下来有 $m$ 行，每行描述一条道路。每行包含三个整数 $a$, $b$ 和 $c$：表示城市 $a$ 和城市 $b$ 之间有一条道路，长度为 $c$。所有道路都是双向的。

然后有 $q$ 行，每行描述一个查询。每行包含两个整数 $a$ 和 $b$：你需要确定城市 $a$ 和城市 $b$ 之间的最短路径长度。

输出格式

对于每个查询，输出两城市之间的最短路径长度。如果没有路径，输出 $−1$。

样例

4 3 5
1 2 5
1 3 9
2 3 3
1 2
2 1
1 3
1 4
3 2

5
5
8
-1
3

说明/提示

$1 \leq n \leq 500$；

$1 \leq m \leq n^2$；

$1 \leq q \leq 10^5$；

$1 \leq a,b \leq n$；

$1 \le c \le 10^9$。