// 差分约束 SPFA 算法 O(NM)
#include<bits/stdc++.h>
using namespace std;

const int N=1005,M=21005;
int h[N],to[M],ww[M],ne[M],idx;
void add(int a,int b,int c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m1,m2;
int d[N],cnt[N];
bool vis[N];

bool spfa(int siz){
  memset(d,0x3f,sizeof d);
  memset(vis,0,sizeof vis);
  memset(cnt,0,sizeof cnt);
  queue<int> q;
  for(int i=1;i<=siz;i++)d[i]=0,q.push(i),vis[i]=true;
  
  while(!q.empty()){
    int u=q.front();q.pop();vis[u]=false;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i];
      if(d[v]>d[u]+ww[i]){
        d[v]=d[u]+ww[i]; //最短路
        cnt[v]=cnt[u]+1; //走过的边数
        if(cnt[v]>=n) return true; //有负环
        if(!vis[v]) q.push(v),vis[v]=true;
      }
    }
  }
  return false;
}
int main(){
  scanf("%d%d%d",&n,&m1,&m2);
  for(int i=1; i<=n; i++){
    add(i,i-1,0); //(i-1)-i<=0
  }
  for(int a,b,c;m1--;){
    scanf("%d%d%d",&a,&b,&c);
    add(a,b,c); //b-a<=c
  }
  for(int a,b,c;m2--;){
    scanf("%d%d%d",&a,&b,&c);
    add(b,a,-c); //a-b<=-c
  }
  
  if(spfa(n)) puts("-1"); //有负环则无解
  else{
    spfa(1);
    if(d[n]==0x3f3f3f3f) puts("-2"); //无穷大
    else printf("%d\n",d[n]);
  }
}

差分约束的做法：转化为 最短路 或 最长路，用spfa跑。
1、求$d_n$最小：跑最长路，要求约束形如 $d_i +w \le d_j$ $\to$ G[i].push_back({j,w}) ；
2、求$d_n$最大：跑最短路，要求约束形如 $d_i + w \ge d_j$ $\to$ G[i].push_back({j,w})；
3、在(1)和(2)的情况下，某个点超过n次进队列则无解；$d_n$若无更新则$d_n$无限制。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
vector< pair<int,int> >G[N];
int n,d[N],dd[N];bool v[N];
int spfa()
{
    memset(d,0x3f,sizeof(d));
    memset(dd,0,sizeof(dd));
    memset(v,0,sizeof(v));
    queue<int>q; 
    for(int i=1;i<=n;i++)q.push(i),v[i]=1;
    d[1]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();v[x]=0;
        for(auto i:G[x])
        {
            int y=i.first,w=i.second;
            if(d[y]>d[x]+w)
            {
                d[y]=d[x]+w;
                dd[y]=dd[x]+1;if(dd[y]>n)return -1;
                if(!v[y])q.push(y),v[y]=1;
            }
        }
    }
    return (d[n]==0x3f3f3f3f)? -2 : d[n];
}
int main()
{
    int m1,m2;scanf("%d %d %d",&n,&m1,&m2);
    for(int i=1,A,B,D;i<=m1;i++)
    {
        scanf("%d %d %d",&A,&B,&D);//xB-xA<=D -> xA+D >=xB;
        G[A].push_back({B,D}); 
    }
    for(int i=1,A,B,D;i<=m2;i++)
    {
        scanf("%d %d %d",&A,&B,&D);//xB-xA>=D -> xB-D >=xA;
        G[ B ].push_back({A,-D}); 
    }
    for(int i=1;i<n;i++)
    {
        G[i+1].push_back({i,0});// x(i+1) + 0 >=xi
    }
    printf("%d\n",spfa());
    return 0;
}