奶牛排队

【题目描述】

像每个人一样，奶牛们喜欢在排队等待领取食物和自己的朋友站在一起。$FJ$ 拥有 $N$ 头奶牛，编号为 $1$ 至 $N$ 。它们站成一行，等待 $FJ$ 派送奶牛营养餐。这些奶牛按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多头奶牛挤在同一位置的情况(也就是说，如果我们认为奶牛位于数轴上，那么多头奶牛的位置坐标可能相同)。

某些奶牛之间互相喜欢，它们希望互相之间的距离至多为一个定值。某些奶牛之间互相厌恶，它们希望互相之间的距离至少为一个定值。现在给定 $X$ 个互相喜爱的奶牛对以及它们之间距离的最大值， $Y$ 个互相厌恶的奶牛对以及它们之间距离的最小值。

你的任务是计算在满足以上条件的前提下，编号为 $1$ 和编号为 $N$ 的奶牛之间距离的最大可能值。

【输入格式】

输入文件第一行三个整数 $N$ , $X$ 以及 $Y$ 。

此后 $X$ 行，每行包含三个用空格分开的整数 $A , B$ 和 $D$，其中 $A , B$ 满足 $A \lt B$。表示编号为 $A$ 和 $B$ 的奶牛之间的距离至多为 $D$。

此后 $Y$ 行，每行包含三个用空格分开的整数 $A , B$ 和 $D$ ，其中 $A , B$ 满足 $A \lt B$。表示编号为 $A$ 和 $B$ 的奶牛之间的距离至少为 $D$。

【输出格式】

输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出 $-1$。如果编号 $1$ 和编号 $N$ 的奶牛间距离可以任意，就输出 $-2$ 。否则输出它们之间的最大可能距离。

【样例输入1】

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

【样例输出1】

27

【样例输入输出2】

点击下载样例2

【数据规模与约定】

对于 $20\%$ 的数据，$1 \leq N,X,Y \leq 20 , 1 \leq D \leq 3000$;

对于 $40\%$ 的数据，$1 \leq N \leq 100,1 \leq X,Y \leq 400 , 1 \leq D \leq 31000$;

对于 $100\%$ 的数据，$1 \leq N \leq 1000,1 \leq X,Y \leq 5000 , 1 \leq D \leq 500000$;

【来源】

中小学电脑报 NOI导刊 NOIP2012河南省实验中学培训 Day4 Exercise Problem 10