裸差分约束。有两种写法。spfa 和 dfs，dfs 优点在判负环，但递归常数巨大，spfa 优点在快。

差分约束就是用最短路的思想来接不等式组，具体做法见。

#include 
    
     using namespace std;#define db double#define ll long long#define RG registerinline int gi(){    RG int ret; RG bool flag; RG char ch;    ret=0, flag=true, ch=getchar();    while (ch < '0' || ch > '9')        ch == '-' ? flag=false : 0, ch=getchar();    while (ch >= '0' && ch <= '9')        ret=(ret<<3)+(ret<<1)+ch-'0', ch=getchar();    return flag ? ret : -ret;}const db pi = acos(-1.0);const int N = 1005, M = 2e4+5, inf = 1<<30;bool vis[N];int f[N],dis[N],et[M],nx[M],ed[M];int num;inline void add(int x,int y,int z){    nx[++num]=f[x], et[num]=y, ed[num]=z, f[x]=num;}inline void spfa(int o){    int i,to,len;    vis[o]=true;    for (i=f[o]; i; i=nx[i])        {            to=et[i], len=ed[i];            if (dis[to] > dis[o]+len)                {                    if (vis[to])                        puts("-1"), exit(0);                    dis[to]=dis[o]+len;                    spfa(to);                }        }    vis[o]=false;}int main(){    freopen("layout.in","r",stdin);    freopen("layout.out","w",stdout);    int n,m,k,i,x,y,z;    n=gi(), m=gi(), k=gi();    for (i=1; i<=m; ++i)        {            x=gi(), y=gi(), z=gi();            add(x,y,z);        }    for (i=1; i<=k; ++i)        {            x=gi(), y=gi(), z=gi();            add(y,x,-z);        }    for (i=2; i<=n; ++i)        dis[i]=inf;    spfa(1);    dis[n] < inf ? printf("%d\n",dis[n]) : puts("-2");    return 0;}