1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 struct edge { int x,y,from,v; }e[60010*2];
 6 int tot,n,boo,to,mx,sum1,sum2,ans,cnt=1,f[60010*15],visit[60010],head[60010],sum[60010],k[60010*15];
 7 void insert(int x,int y,int v) { e[++cnt].y=y; e[cnt].x=x; e[cnt].from=head[x]; head[x]=cnt; e[cnt].v=v; }
 8 void dfs(int x,int k)
 9 {
10     visit[x]=1;
11     for (int i=head[x];i;i=e[i].from)
12         if ((i^1)!=k)
13             if (!visit[e[i].y]) sum[e[i].y]=sum[x]+e[i].v,mx+=e[i].v,dfs(e[i].y,i);
14             else 
15                 if (i/2!=to/2)
16                 {
17                     if (boo) { printf("-1"),exit(0); }
18                     boo=1,to=i;
19                 }
20 }
21 int main()
22 {
23     scanf("%d",&n);
24     for (int i=1;i<=2*n;i++)
25     {
26         int l,r,s;
27         scanf("%d%d%d",&l,&r,&s);
28         insert(l,r+n,-s),insert(r+n,l,s);
29     }
30     for (int i=1;i<=2*n;i++)
31         if (!visit[i])
32         {
33             boo=mx=to=0;
34             dfs(i,0);
35             int a=mx-2*sum[e[to].x]-e[to].v,b=mx-2*sum[e[to].y]+e[to].v;
36             if (a>b) swap(a,b);
37             k[b-=a]++,sum1+=a,sum2+=b;
38             
39         }
40     f[0]=1,ans=abs(sum1);
41     for (int i=1;i<=sum2;i++)
42         if (k[i])
43             for (int j=sum2;j>=0;j--)
44                 if (f[j])
45                     for (int z=1;z<=k[i]&&!f[i*z+j];z++) f[i*z+j]=1;
46     for (int i=1;i<=sum2;i++) if (f[i]) ans=min(ans,abs(sum1+i));
47     printf("%d",ans);
48     return 0;
49 }