import sys
'''
将1号节点固定在0位置,构造超级源点建图,单源最短路求最大解,如果图里面有负环,则无解
如果最大解最后一个数值能够到0x7ffffffe, 则最前面和最后面的奶牛之间的距离可以无穷大
剩下的情况就是正常的查分约束的解
'''
from collections import deque
class SPFA:
# start_node 为起始点,edges是边的三元组(节点1, 节点2, 边权重) is_directed表示是否是有向图
# 包含节点为1, 2, 3, 4, ..... max_node_num
def __init__(self, start_node, edges, is_directed, max_node_num):
self.edges = edges[::]
self.start_node = start_node
self.is_directed = is_directed
self.max_node_num = max_node_num
# 获取最短路径长度的列表[(节点1,长度1), (节点2, 长度2) .....]
def getMinPathLen(self):
return self.getInfo(min_path=True)
# 获取最长路径长度列表[(节点1,长度1), (节点2, 长度2) .....]
def getMaxPathLen(self):
return self.getInfo(min_path=False)
# min_path表示求的是最短路径还是最长路径
def getInfo(self, min_path = True):
link = {}
dis = [0x7fffffff] * (self.max_node_num+1) if min_path else [-0x7fffffff] * (self.max_node_num+1)
dis[self.start_node] = 0
for a, b, w in self.edges:
if not self.is_directed:
# 无向图检查是否有负边
if (min_path == True and w < 0) and (min_path == False and w > 0):
# 有正环或者负环提前退出
return None
if a not in link:
link[a] = []
if b not in link:
link[b] = []
link[a].append((b, w))
link[b].append((a, w))
else:
if a not in link:
link[a] = []
link[a].append((b, w))
updated_nodes = deque()
updated_nodes.append(self.start_node)
in_que = [0] * (self.max_node_num + 1)
in_que[self.start_node] = 1
# 进行V次迭代,第V次检查是否是无解情况
iter_times = 0
cnt = [0] * (self.max_node_num + 1)
while iter_times < self.max_node_num:
update_flag = False
# 利用上一轮迭代距离变小的点进行松弛操作
node_num = len(updated_nodes)
for _ in range(node_num):
a = updated_nodes.popleft()
in_que[a] = 0
if a not in link:
continue
for b, w in link[a]:
if dis[a] == 0x7fffffff:
if w == -0x7fffffff:
new_dis = 0
else:
new_dis = 0x7fffffff
elif dis[a] == -0x7fffffff:
if w == 0x7fffffff:
new_dis = 0
else:
new_dis = -0x7fffffff
else:
new_dis = dis[a] + w
if (min_path == True and new_dis < dis[b]) or (min_path == False and new_dis > dis[b]):
dis[b] = new_dis
cnt[b] = cnt[a] + 1
update_flag = True
if cnt[b] >= self.max_node_num:
return None
if in_que[b] == 0:
in_que[b] = 1
updated_nodes.append(b)
iter_times += 1
if iter_times == self.max_node_num:
if update_flag:
return None
if not update_flag:
break
return dis
edges = []
n, m1, m2 = map(int, input().split())
for i in range(m1):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a
# val(b) - val(a) <= w
edges.append((a, b, w))
for i in range(m2):
a, b, w = map(int, input().split())
if a > b:
a, b = b, a
# val(b) - val(a) >= w
edges.append((b, a, -w))
for i in range(2, n+1):
# 后一个要大于等于前一个
# val(i) >= val(i-1)
edges.append((i, i-1, 0))
# 从2开始的每一个点都小于等于一个极大值,这样才能让超级源点对每一个点都是可达的,注意这里不能取0x7fffffff, 这个数值表示的是不可达
edges.append((n+1, i, 0x7ffffffe))
# 超级源点是n+1, 要求1号点固定在0位置
edges.append((1, n+1, 0))
edges.append((n+1, 1, 0))
# print(edges)
algo = SPFA(n+1, edges, is_directed=True, max_node_num=n+1)
ans = algo.getMinPathLen()
if ans is None:
print(-1)
else:
if ans[n] == 0x7ffffffe:
print(-2)
else:
print(ans[n])