两类最短路查询¶

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

实际时限以标准程序在目标评测环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。

背景故事¶

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

(本故事由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\) .

4 3 1
1 2 1000000000
2 3 1000000000
3 4 1000000000
1 4

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\) .图不保证连通。