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

---

题目描述

正如其他物种一样，奶牛们也喜欢在排队打饭时与它们的朋友挨在一起。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<B\le N,\) \(1\le D\le 10^6\)。

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

27

说明/提示

样例解释：

共有 \(4\) 头奶牛。\(1\) 号奶牛和 \(3\) 号奶牛必须相距不超过 \(10\) 个单位长度，\(2\) 号奶牛和 \(4\) 号奶牛必须相距不超过 \(20\) 个单位长度，而 \(2\) 号奶牛与 \(3\) 号奶牛相互讨厌，必须相距不少于 \(3\) 个单位长度。

最佳方案是将奶牛们按以下坐标放置于一条数轴上：\(1\) 号奶牛在 \(0\) 处，\(2\) 号奶牛在 \(7\) 处，\(3\) 号奶牛在 \(10\) 处，\(4\) 号奶牛在 \(27\) 处。