题目描述

给出一个 $n$ 个点、$m$ 条边的无向图，边权均为正整数。接下来有 $q$ 次询问，每次给出 $u,v$，请你回答 $u$ 到 $v$ 的最短路径长度。

输入格式

第一行三个整数 $n,m,q$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示连接 $u,v$ 的长度为 $w$ 的无向边。图中可能有重边和自环。

接下来 $q$ 行，每行两个整数 $u,v$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数表示对应询问的最短路径长度；若 $u$ 与 $v$ 不连通则输出 $-1$。

输入输出样例 #1

输入 #1

3 3 2
1 2 5
2 3 6
1 3 20
1 3
2 3

输出 #1

11
6

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 400$，$0\le m\le 10^5$，$1\le q\le 10^5$，$1\le w\le 10^4$。