说明

    和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。
    约翰的编号为1到n的n（2<=n<=1000）只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序必须和她们编号的顺序一致。有M对奶牛互相爱慕，她们之间的距离不能超过一定的值，有K对奶牛互相敌视，她们的距离不能小于一定的值。
    那么，首尾奶牛的最大距离是多少呢？

输入格式

第一行输入n，M,K，接下来M行每行三个整数x,y,z，表示编号为x和y的两头奶牛之间的距离最大不超过z，再接下来K行每行三个整数a,b,c，表示编号为a和b的两头奶牛之间的距离最少为c。

输出格式

如果没有合理方案，输出-1，如果首尾两头牛的距离可以无限大，输出-2，否则输出一个整数表示首尾奶牛的最大距离。

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

27

提示

样例说明：
四只牛分别在0,7,10,27。

来源

图论 洛谷