为了随时与 rainbow 快速交流，Freda 制造了两部传呼机。
Freda 和 rainbow 所在的地方有 N 座房屋、M 条双向光缆。
每条光缆连接两座房屋，传呼机的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费 t 单位时间。
现在 Freda 要进行 Q 次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。
N 座房屋通过光缆一定是连通的，并且这 M 条光缆有以下三类连接情况：
请你帮帮他们。
第一行包含三个用空格隔开的整数 N、M 和 Q。
接下来 M 行每行三个整数 x、y、t，表示房屋 x 和 y 之间有一条传递时间为 t 的光缆。
最后 Q 行每行两个整数 x、y，表示 Freda 想知道在 x 和 y 之间传呼最少需要多长时间。
输出 Q 行，每行一个整数，表示 Freda 每次试验的结果。
5 4 2 1 2 1 1 3 1 2 4 1 2 5 1 3 5 2 1
3 1