记录编号	538670	评测结果	AAAAAAAAAA
题目名称	[WC 2010模拟] 奶牛排队	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.022 s
提交时间	2019-07-29 11:04:15	内存使用	13.92 MiB

//求最大值，    B-A<=C A->B 长度为C,最短路 
//求最小值      B-A>=C A->B 长度为C,最长路
//负环或者正环 ，无解
//更新不到dis[T] 任意解 
#include <deque>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 1e9
const int maxn=1500;
const int maxm=10500;
struct Edge{
	int to,next,dis;
}e[maxm<<1];
int len,head[maxn];
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].dis=z;e[len].next=head[x];head[x]=len;
}
int n,m1,m2;
int dis[maxn];
bool flag[maxn];
deque<int> q;
int num[maxn];
void Spfa(int x){
	memset(dis,0x3f,sizeof(dis));dis[x]=0;
	memset(flag,0,sizeof(flag));flag[x]=true;
	q.push_front(x);
	while(!q.empty()){
		int k=q.front();q.pop_front();
		flag[k]=false;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(dis[j]>dis[k]+e[i].dis){
				dis[j]=dis[k]+e[i].dis;
				if(!flag[j]){
					flag[j]=true;
					if(!q.empty() && dis[q.front()]>dis[j]) q.push_front(j);
					else q.push_back(j);
					num[j]++;
					if(num[j]>=n) {dis[n]=-1;return;}
				}
			}
		}
	}
}
void Init();
int main(){
	freopen("layout.in","r",stdin);
	freopen("layout.out","w",stdout); 
	Init();
	return 0;
}
void Init(){
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		if(x>y) swap(x,y);
		Insert(x,y,z); 
	}
	for(int i=1;i<=m2;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		if(x>y) swap(x,y);
		Insert(y,x,-z); 
	}
	Spfa(1);
	if(dis[n]==dis[n+1]) puts("-2");
	else printf("%d\n",dis[n]);
}