# 两类最短路查询

预估时间限制：1 秒。内存限制：128 MB。

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

路线服务需要回答站点之间的最短路查询。有些网络很大，但只询问一次；其余网络的站点较少，可以提出许多查询。

(本故事由GPT-6重写)

## 形式化问题描述

给定有 $n$ 个点、$m$ 条非负权无向边的图，点编号为 $1,\ldots,n$ .依次回答 $q$ 次询问，每次给出两个点，求它们之间的最短路径权值，即边权之和的最小值。若不可达，输出 $-1$ .

所有输入都满足 $q=1$ 或 $n\le500$ .允许重边、自环、零权边和重复询问。从一个点到自身可以不经过任何边，因此距离为零。

## 输入格式

第一行三个整数 $n,m,q$ .接下来 $m$ 行，每行三个整数 $u,v,c$ ，表示 $u,v$ 之间有一条权值为 $c$ 的无向边。再接下来 $q$ 行，每行两个整数 $u,v$ ，表示一次询问。

## 输出格式

按输入顺序输出 $q$ 行，每行给出一次询问的最短路径权值；不可达时输出 $-1$ .

## 样例

### 样例 1

### 输入

```text
4 4 4
1 2 9
1 2 2
2 3 4
1 3 10
1 3
3 1
1 4
4 4
```

### 输出

```text
6
6
-1
0
```

### 样例 2

### 输入

```text
4 3 1
1 2 1000000000
2 3 1000000000
3 4 1000000000
1 4
```

### 输出

```text
3000000000
```

## 样例解释

第一组中，点 $1,2$ 之间两条边可以选择权值为二的那条，再经过权值为四的边到达点 $3$ ，得到距离六。无向图中的反向查询也为六。点 $4$ 与其余点不连通，但它到自身的距离为零。

第二组只有一条连接点 $1,4$ 的简单路径，权值之和为 $3000000000$ .

## 数据范围与保证

对所有数据，$1\le n,m,q\le5\times10^5$ ，$1\le u,v\le n$ ，$0\le c\le10^9$ ，并且 $q=1$ 或 $n\le500$ .图不保证连通。

| 分值比例 | 额外条件 |
| --- | --- |
| 30% | $q=1$ |
| 40% | $q=1$ ，且 $n\le500$ |
| 30% | $n\le500$ |