原题来自：USACO 2005 Dec. Gold
FJ 有 N 头奶牛 (2\le N\le 1000) ，编号为 1\ldots N 。奶牛们将按照编号顺序排成一列队伍（可能有多头奶牛在同一位置上）。换句话说，假设 i 号奶牛位于 P_{\!\;i} ，则 P_{\,1}\le P_{\,2}\le \ldots\le P_{\!\;N} 。
有些奶牛是好基友，它们希望彼此之间的距离小于等于某个数。有些奶牛是情敌，它们希望彼此之间的距离大于等于某个数。
给出 M_L 对好基友的编号，以及它们希望彼此之间的距离小于等于多少；又给出 M_D 对情敌的编号，以及它们希望彼此之间的距离大于等于多少 (1\le M_L, M_D\le 10^4) 。
请计算：如果满足上述所有条件， 1 号奶牛和 N 号奶牛之间的距离（ P_{\!\;N}-P_{\,1} ）最大为多少。
第一行：三个整数 N, M_L, M_D ，用空格分隔。 第 2\dots M_L+1 行：每行三个整数 A, B, D ，用空格分隔，表示 P_A-P_B\le D 。 第 M_L+2\dots M_L+M_D+1 行：每行三个整数 A, B, D ，用空格分隔，表示 P_A-P_B\ge D 。 保证 1\le A<B\le N, 1\le D\le 10^6 .
一行，一个整数。如果没有合法方案，输出 \texttt{-1} . 如果有合法方案，但 1 号奶牛可以与 N 号奶牛相距无穷远，输出 \texttt{-2} . 否则，输出 1 号奶牛与 N 号奶牛间的最大距离。
4 2 1 1 3 10 2 4 20 2 3 3
27
这四头牛分别位于 0,7,10,27 。
对于全部数据， 2\le N\le 1000,1\le M_L,M_D\le 10^4,1\le L,D\le 10^6 。