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

---

【题目描述】

　　Czy喜欢将他的妹子们排成一队。假设他拥有 \(N\) 只妹纸，编号为 1 至 \(N\)。Czy让他们站成一行，等待自己来派送营养餐。这些妹纸按照编号大小排列，并且由于它们都很想早点吃饭，于是就很可能出现多只妹纸挤在同一位置的情况(也就是说，如果我们认为妹纸位于数轴上，那么多只妹纸的位置坐标可能相同)。

　　因为众所周知的原因，某些妹纸之间互相喜欢，他们希望互相之间的距离至多为一个定值。但某些妹纸之间互相厌恶，他们希望互相之间的距离至少为一个定值。现在给定 \(ML\) 个互相喜爱的妹纸对以及他们之间距离的最大值，\(MD\) 个互相厌恶的妹纸对以及他们之间距离的最小值。

　　你的任务是计算在满足以上条件的前提下，帮助Czy计算出编号为 1 和编号为 \(N\) 的妹纸之间距离的最大可能值。

【输入格式】

　　第一行有 3 个整数，每两个整数之间用一个空格隔开，依次表示 \(N,ML\) 和 \(DL\) ；
　　此后 \(ML\) 行，每行包含三个用空格分开的整数 \(A,B\) 和 \(D\)，其中 \(A,B\) 满足 \(1<=A<=B<=N\)。表示编号为 \(A\) 和 \(B\) 的妹纸之间的距离至多为 \(D\)。
　　此后 \(MD\) 行，每行包含三个用空格分开的整数 \(A,B\) 和 \(D\)，其中 \(A,B\) 满足 \(1<=A<=B<=N\)。表示编号为 \(A\) 和 \(B\) 的妹纸之间的距离至少为 \(D\)。

【输出格式】

　　输出文件仅包含一个整数。如果不存在任何合法的排队方式，就输出-1。如果编号 1 和编号 \(N\) 的妹纸间距离可以任意，就输出-2 。否则输出他们之间的最大可能距离。

【输入输出样例】

　Input

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

　Output

27

【数据限制】

　　对于 \(40\%\) 的数据，\(1≤N≤100\)
　　对于 \(100\%\) 的数据，\(1≤N≤1000\)，\(3≤ML,MN≤10000\)，\(D≤1000000\)

【来源】

　　Mr.he