Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。

奶牛的训练场中有 N (1 <= N <= 300) 个站台，分别标记为 1..N。所有站台之间有 M (1 <= M <= 25,000) 条单向路径，第 i 条路经是从站台 Si 开始，到站台 Ei，其中最高的栏的高度为 Hi (1 <= Hi <= 1,000,000)。

无论如何跑，奶牛们都要跨栏。奶牛们有 T (1 <= T <= 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 <= Ai <= N; 1 <= Bi <= N)，表示奶牛必须从站台 Ai 跑到站台 Bi，可以路过别的站台。奶牛们想找一条路径从站台 Ai 到站台 Bi，使路径上最高的栏的高度最小。你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。

行 1：两个整数 N, M, T。

行 2..M+1：包含三个整数 Si , Ei , Hi。

行 M+2..M+T+1：包含两个整数，表示每个任务的起始站台和目标站台: Ai , Bi。

输出 T 行，每行一个整数，表示每个任务路径上最高的栏的高度的最小值。如果无法到达，输出 -1。