P4878 [USACO05DEC] Layout G

14组数据，前10组为原数据，后4组为hack数据

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。FJ 有编号为 $1\dots N$ 的 $N$ 头奶牛 $(2\le N\le 1000)$。奶牛们始终需要按照编号顺序来排队。奶牛们很笨拙，因此可能有多头奶牛在同一位置上。 有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。 给出 $M_L$ 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 $M_D$ 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 $(1\le M_L,$ $M_D\le 10^4)$。 请计算：如果满足上述所有条件，$1$ 号奶牛和 $N$ 号奶牛之间的距离最大为多少。

第一行：三个整数 $N, M_L, M_D$，用空格分隔。 第 $2\dots M_L+1$ 行：每行三个整数 $A, B, D$，用空格分隔，表示 $A$ 号奶牛与 $B$ 号奶牛之间的距离须 $\le D$。保证 $1\le A

一行，一个整数。如果没有合法方案，输出 `-1`. 如果有合法方案，但 $1$ 号奶牛可以与 $N$ 号奶牛相距无穷远，输出 `-2`. 否则，输出 $1$ 号奶牛与 $N$ 号奶牛间的最大距离。

样例解释： 共有 $4$ 头奶牛。$1$ 号奶牛和 $3$ 号奶牛必须相距不超过 $10$ 个单位长度，$2$ 号奶牛和 $4$ 号奶牛必须相距不超过 $20$ 个单位长度，而 $2$ 号奶牛与 $3$ 号奶牛相互讨厌，必须相距不少于 $3$ 个单位长度。 最佳方案是将奶牛们按以下坐标放置于一条数轴上：$1$ 号奶牛在 $0$ 处，$2$ 号奶牛在 $7$ 处，$3$ 号奶牛在 $10$ 处，$4$ 号奶牛在 $27$ 处。