6471: layout
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：0
题目描述
和人类一样，奶牛们在打饭的时候喜欢和朋友站得很近。
约翰的编号为1到n的n（2<=n<=1000）只奶牛正打算排队打饭。现在请你来安排她们，让她们在数轴上排好队。奶牛的弹性很好，同一个坐标可以站无限只奶牛，排队的顺序必须和她们编号的顺序一致。有M对奶牛互相爱慕，她们之间的距离不能超过一定的值，有K对奶牛互相敌视，她们的距离不能小于一定的值。
那么，首尾奶牛的最大距离是多少呢？
约翰的编号为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。
四只牛分别在0,7,10,27。