题目描述

有 $n$ 头牛按编号顺序排成一列，编号从 $1$ 到 $n$。每头牛站在数轴上的某个位置（可以有多头牛在同一位置）。

给定两类约束：

• $ML$ 条友好约束：牛 $A$ 和牛 $B$（$A \lt B$）之间的距离不超过 $D$；
• $MD$ 条排斥约束：牛 $A$ 和牛 $B$（$A \lt B$）之间的距离至少为 $D$。

另外，由于排队顺序固定，编号小的牛不能排在编号大的牛后面（即位置 $pos_i \le pos_{i+1}$）。

请计算在满足所有约束的前提下，牛 $1$ 和牛 $n$ 之间的最大距离。如果无解输出 $-1$，如果距离可以任意大输出 $-2$。

输入格式

第一行三个整数 $N, ML, MD$，分别表示牛的数量、友好约束数和排斥约束数。

接下来 $ML$ 行，每行三个整数 $A, B, D$（$1 \le A \lt B \le N$），表示牛 $A$ 和牛 $B$ 的距离不超过 $D$。

再接下来 $MD$ 行，每行三个整数 $A, B, D$（$1 \le A \lt B \le N$），表示牛 $A$ 和牛 $B$ 的距离至少为 $D$。

输出格式

输出一行一个整数：无解输出 $-1$，距离无上界输出 $-2$，否则输出牛 $1$ 和牛 $n$ 的最大距离。

样例

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

27

提示

对于 $100\%$ 的数据，$2 \le N \le 1000$，$1 \le ML, MD \le 10000$，$1 \le D \le 10^6$。

样例解释：最优方案是牛 1 在位置 0，牛 2 在位置 7，牛 3 在位置 10，牛 4 在位置 27。