题意：
有n个士兵，你可以选择让它成为战士还是法师。
有m对关系，u和v 如果同时为战士那么你可以获得a的权值
如果同时为法师，你可以获得c的权值，
如果一个为战士一个是法师，你可以获得b的权值
问你可以获得的最大权值是多少？
题解：
对每个士兵建立一个点x ，点x 向源点s 连一条边，向汇点t 连一条边，
分别表示选择两种职业，然后就可以先加上所有的贡献，通过两点关系用 最小割建模，如下图所示
设一条边的三种贡献为A, B, C，可以得到以下方程：
如果x,y都是法师，你可以获得C的权值，但是我们构建的是最小割模型（这个权值C应该是A+B+C-该图的最小割），
我们选择x,y都是法师的最小割对应的权值应该是A+B，对应的边根据上述是a,b
所以有a+b=A+B
同理对于都是战士有公式c+d=B+C
对于一战士一法师有公式a+e+d=A+C b+e+c=A+C
存在一组解
a=b=(A+B)/2,c=d=(C+B)/2,e=-B+（A+C)/2；
为了消除浮点数的问题，我们建边的时候将边权*2，取答案的时候/2即可
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map> #define pi acos(-1.0)
#define eps 1e-9
#define fi first
#define se second
#define rtl rt<<1
#define rtr rt<<1|1
#define bug printf("******\n")
#define mem(a, b) memset(a,b,sizeof(a))
#define name2str(x) #x
#define fuck(x) cout<<#x" = "<<x<<endl
#define sfi(a) scanf("%d", &a)
#define sffi(a, b) scanf("%d %d", &a, &b)
#define sfffi(a, b, c) scanf("%d %d %d", &a, &b, &c)
#define sffffi(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
#define sfL(a) scanf("%lld", &a)
#define sffL(a, b) scanf("%lld %lld", &a, &b)
#define sfffL(a, b, c) scanf("%lld %lld %lld", &a, &b, &c)
#define sffffL(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
#define sfs(a) scanf("%s", a)
#define sffs(a, b) scanf("%s %s", a, b)
#define sfffs(a, b, c) scanf("%s %s %s", a, b, c)
#define sffffs(a, b, c, d) scanf("%s %s %s %s", a, b,c, d)
#define FIN freopen("../in.txt","r",stdin)
#define gcd(a, b) __gcd(a,b)
#define lowbit(x) x&-x
#define IO iOS::sync_with_stdio(false) using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const ULL seed = ;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int maxn = + ;
const int maxm = 2e5 + ;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
int n, m; struct MaxFlow {
struct Edge {
int v, nxt;
LL w;
} edge[maxm];
int tot, num, s, t;
int head[maxn]; void init() {
memset(head, -, sizeof(head));
tot = ;
} void add(int u, int v, LL w) {
edge[tot] = (Edge) {
v, head[u], w
};
head[u] = tot++;
edge[tot] = (Edge) {
u, head[v],
};
head[v] = tot++;
} int d[maxn], vis[maxn], gap[maxn]; void bfs() {
memset(d, , sizeof(d));
memset(gap, , sizeof(gap));
memset(vis, , sizeof(vis));
queue<int> q;
q.push(t);
vis[t] = ;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (!vis[v]) {
d[v] = d[u] + ;
gap[d[v]]++;
q.push(v);
vis[v] = ;
}
}
}
} int last[maxn]; LL dfs(int u, LL f) {
if (u == t) return f;
LL sap = ;
for (int i = last[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].w > && d[u] == d[v] + ) {
last[u] = i;
LL tmp = dfs(v, min(f - sap, edge[i].w));
edge[i].w -= tmp;
edge[i ^ ].w += tmp;
sap += tmp;
if (sap == f) return sap;
}
}
if (d[s] >= num) return sap;
if (!(--gap[d[u]])) d[s] = num;
++gap[++d[u]];
last[u] = head[u];
return sap;
} LL solve(int st, int ed, int n) {
LL flow = ;
num = n;
s = st;
t = ed;
bfs();
memcpy(last, head, sizeof(head));
while (d[s] < num) flow += dfs(s, INFLL);
return flow;
}
} F; int main() {
//FIN;
while (~sffi(n, m)) {
F.init();
LL sum = ;
for (int i = , u, v, a, b, c; i < m; ++i) {
sffi(u, v);
sfffi(a, b, c);
F.add(, u, a + b);
F.add(, v, a + b);
F.add(u, n + , b + c);
F.add(v, n + , b + c);
F.add(u, v, - * b + a + c);
F.add(v, u, - * b + a + c);
sum += a + b + c;
}
printf("%lld\n", ( * sum - F.solve(, n + , n + )) / );
}
return ;
}