时间限制：1秒　　内存限制：256M

---

【题目描述】

　　如果一个系统由 \(n\) 个变量和 \(m\) 个约束条件组成，其中每个约束条件形如 \(x_j-x_i≤bk(i,j∈[1,n],k∈[1,m])\)，则称其为差分约束系统。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

　　下面是关于差分约束系统一个实际问题的描述：

　　FJ有 \(n\) 头奶牛（编号从 \(1\) 到 \(n\)），沿一条直线站着等候喂食，由于奶牛们身材都比较苗条，所以可能有多头奶牛站在同一个位置的情况。设第 \(i\) 头奶牛站队位置为 \(d[i]\)，在安排每头奶牛站队位置 \(d[i]\) 时需要满足如下的条件：

　　1、奶牛应按照编号顺序站队，即 \(d[i]-d[i+1]≤0\)。

　　2、\(m\) 对友好的牛希望彼此站的近些。即对于友好关系 \((i,j,D)\) 有 \(d[j]-d[i]≤D（1 ≤ i < j ≤ n）\)。

　　3、\(p\) 对敌对的牛希望彼此站的远些。即对于敌对关系 \((i,j,L)\) 有 \(d[j]-d[i]≥L（1 ≤ i < j ≤ n）\)。

　　现在请你帮助FJ判断是否存在满足这些条件的一种站队方案，如果存在请计算 \(1\) 号奶牛与 \(n\) 号奶牛之间的最大距离。如果不存在满足要求的方案，输出 -1；如果 1 号奶牛和N号奶牛间的距离可以任意大，输出 -2；

【输入格式】

　　第 1 行输入 \(n,m,p\)，接下来的 \(m\) 行，每行三个整数 \(i,j,D\)，表示牛 \(i\) 和牛 \(j\) 的距离最多为 \(D\)，再接下来的 \(p\) 行，每行三个整数 \(i,j,L\)，表示牛 \(i\) 和牛 \(j\) 的距离最少为 \(L\)。

【输出格式】

　　如果不存在满足要求的方案，输出 -1；如果 1 号奶牛和 \(N\) 号奶牛间的距离可以任意大，输出-2；否则，计算出在满足所有要求的情况下，1 号奶牛和 \(N\) 号奶牛间可能的最大距离。

【输入输出样例】

　Input

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

　Output

27

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤n≤1000\)，\(1≤m,p≤10000\)，\(1≤D,L≤1000000\)。

【来源】

　　Mr.he