d_x <= d_(x+1) --> d_x <= d_(x+1) + 0
d_y - d_x <= maxd --> d_y <= d_x +maxd
d_y - d_x >= mind --> d_x <= d_y - mind
-----------
const int maxn=4100;
const int maxm=180000;
int n;
struct EdgeNode{
int to;
int w;
int next;
};
struct BellmanFord{
EdgeNode edges[maxm];
int head[maxn],edge,n;
bool vis[maxn];
int outque[maxn];
queue<int>que;
int dis[maxn];
void addedge(int u,int v,int c){
edges[edge].w=c,edges[edge].to=v,edges[edge].next=head[u],head[u]=edge++;
}
void init(int n){
memset(head,-1,sizeof(head));
edge=0;
this->n=n;
}
bool spfa(int s){
int u;
for (int i=0;i<=n;i++) dis[i]=INF;
memset(vis,0,sizeof(vis));
memset(outque,0,sizeof(outque));
while (!que.empty()) que.pop();
que.push(s);
vis[s]=true;
dis[s]=0;
while (!que.empty()){
u=que.front();
que.pop();
vis[u]=false;
outque[u]++;
if (outque[u]>n) return false;
for (int i=head[u];i!=-1;i=edges[i].next){
int v=edges[i].to;
int w=edges[i].w;
if (dis[v]==INF||dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
if (!vis[v]){
vis[v]=true;
que.push(v);
}
}
}
}
return true;
}
}g;
int ml,md;
int main(){
while (~scanf("%d%d%d",&n,&ml,&md)){
g.init(n);
for (int i=1;i<n;i++){
g.addedge(i+1,i,0);
}
for (int i=0;i<ml;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g.addedge(x,y,z);
}
for (int i=0;i<md;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
g.addedge(y,x,-z);
}
if (g.spfa(1)){
if (g.dis[n]==INF) printf("-2
");
else printf("%d
",g.dis[n]);
}
else{
printf("-1
");
}
}
return 0;
}
-----------