题目描述

当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。${FJ}$有${N（}$${2<=N<=1000）}$头奶牛，编号从${1}$到${N，}$沿一条直线站着等候喂食。奶 牛排在队伍中的顺序和它们的编号是相同的。因为奶牛相当苗条，所以可能有两头或者更多奶牛站在同一位置上。

即使说，如果我们想象奶牛是站在一条数轴上的话，允许有两头或更多奶牛拥有相同的横坐标。一些奶牛相互间存有好感，它们希望两者之间的距离不超过一个给定的数${L}$。另一方面，一些奶牛相互间非常反感，它们希望两者间的距离不小于一个给定的数${D}$。

给出${ML}$条关于两头奶牛间有好感的描述，再给出${MD}$条关于两头奶牛间存有反感的描述。${（1<=ML,MD<=10000，}$${1<=L,D<=1000000）}$你的工作是：

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

输入格式

第${1 }$行：三个以空格分隔的整数：${N}$、${ML }$和 ${MD}$。

第${2...ML+1 }$行：

每行包含三个以空格分隔的正整数：${A}$、${B }$和 ${D，}$其中 ${1 <= A < B <= N}$。奶牛 ${A }$和 ${B }$最多只 能是 ${D (1 <= D <= 1,000,000) }$分开。

第${ML+2..ML+MD+1 }$行：

每行包含三个以空格分隔的正整数：${A}$、${B }$和 ${D，}$其中 ${1 <= A < B <= N}$。

奶牛 ${A }$和 ${B }$必 须至少为 ${D (1 <= D <= 1,000,000) }$分开。

输出格式

第${1}$行：单个整数。如果不可能排列，则输出${-1}$。

如果奶牛${1}$和${N}$可以任意相距，则输出${-2}$。否则，输出奶牛${1}$和${N}$之间的最大可能距离

样例

输入样例

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

输出样例

27

提示

输入详细信息：

有${4}$头牛。奶牛${1}$号和${3}$号不得超过${10}$头除此之外，奶牛${2}$和${4}$之间的距离不得超过${20}$个单位，并且奶牛#${2}$和#${3}$彼此不喜欢，且相距不得少于${3}$个单位。