[Usaco2005 dec]Layout 排队布局

当排队等候喂食时，奶牛喜欢与朋友站得近一些。FJ 有 $N$ 头奶牛，编号为 $1$ 到 $N$，它们沿一条直线按照编号顺序排队。多头奶牛可以站在同一位置。

一些奶牛彼此有好感，希望它们之间的距离不超过给定值；另一些奶牛彼此反感，希望它们之间的距离不小于给定值。

现给出 $M_L$ 条关于有好感的奶牛之间最大距离的限制，以及 $M_D$ 条关于相互反感的奶牛之间最小距离的限制。请判断是否存在满足所有限制的排列，并求出在满足所有限制的情况下，奶牛 $1$ 与奶牛 $N$ 之间的最大可能距离。

如果不存在满足所有限制的排列，输出 $-1$；如果奶牛 $1$ 与奶牛 $N$ 之间的距离可以任意大，输出 $-2$。

输入格式

第一行包含三个以空格分隔的整数 $N$、$M_L$ 和 $M_D$。

接下来 $M_L$ 行，每行包含三个以空格分隔的正整数 $A$、$B$ 和 $D$，表示奶牛 $A$ 与奶牛 $B$ 之间的距离至多为 $D$。

随后 $M_D$ 行，每行包含三个以空格分隔的正整数 $A$、$B$ 和 $D$，表示奶牛 $A$ 与奶牛 $B$ 之间的距离至少为 $D$。

输出格式

输出一个整数：

• 如果不存在满足所有限制的排列，输出 $-1$；
• 如果奶牛 $1$ 与奶牛 $N$ 之间的距离可以任意大，输出 $-2$；
• 否则，输出奶牛 $1$ 与奶牛 $N$ 之间的最大可能距离。

样例输入

4 2 1
1 3 10
2 4 20
2 3 3

样例输出

27

数据范围

• $2\le N\le 10^3$；
• $1\le M_L,M_D\le 10^4$；
• 对于每条限制，$1\le A<B\le N$；
• 对于每条限制中的距离 $D$，$1\le D\le 10^6$。

来源与许可

本题为 USACO 2005 December 试题「Layout 排队布局」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 2 1
1 3 10
2 4 20
2 3 3

输出

27