CF687D Dividing Kingdom II

很久以前，有一个伟大的王国，由伟大的 Arya 和伟大的 Pari 共同统治。这两位对于他们喜欢的数字存在一些分歧，于是决定将王国分成两部分。 这个伟大的王国有 $n$ 个城市，编号从 $1$ 到 $n$，有 $m$ 条双向道路，编号从 $1$ 到 $m$。第 $i$ 条道路长度为 $w_{i}$。Arya 和 Pari 想要选择析构掉一些前缀道路（编号小于某个 $x$ 的所有道路）和一些后缀道路（编号大于某个 $x$ 的所有道路），这样只剩下道路 $l,l+1,...,r-1$ 和 $r$。 之后，他们将把王国一分为二（每个城市只属于其中一部分），使得分割的“困难度”最小。一次划分的困难度定义为：在分开的同一部分中，所有道路长度的最大值。如果不存在这样的道路，则困难度视为 $-1$。 历史学家发现了王国的地图，他们有 $q$ 个关于 $l$ 和 $r$ 这些值的猜测。对于每一组猜测 $l_{i}$ 和 $r_{i}$，请输出在上述情况下王国划分的最小可能困难度。

第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, q \leq 1000$，$n-1 \leq m \leq \binom{n}{2}$）——分别代表王国的城市数、道路数和历史学家的猜测数量。 接下来的 $m$ 行中，第 $i$ 行包含三个整数 $u_{i}$、$v_{i}$ 和 $w_{i}$（$1 \leq u_{i}, v_{i} \leq n, 0 \leq w_{i} \leq 10^{9}$），表示编号为 $i$ 的道路连接城市 $u_{i}$ 和 $v_{i}$，长度为 $w_{i}$。保证没有道路连接同一个城市，也没有两座城市之间有多条道路。 接下来的 $q$ 行中，每行包含两个整数 $l_{i}$ 和 $r_{i}$（$1 \leq l_{i} \leq r_{i} \leq m$），为历史学家的一个猜测，表示王国只剩下编号在 $[l_{i}, r_{i}]$ 范围内的道路。

对于每一个猜测，输出一行，表示在描述情形下王国划分的最小可能困难度。

由 ChatGPT 5 翻译