//teshuxingzhi #include <bits/stdc++.h> using namespace std; int T,n,m,p[114514][5],rem[114514],a[114514]; int dfs(int x,int c) { if(x==m) { return c; } int cnt=0; for(int i=1;i<=m;i++) { if(rem[i]==0) { int ra=a[p[i][1]],rb=a[p[i][3]]; a[p[i][1]]=p[i][2],a[p[i][3]]=p[i][4]; rem[i]=x; cnt=max(cnt,dfs(x+1,c+p[i][2]-ra+p[i][4]-rb)); rem[i]=0; a[p[i][1]]=ra,a[p[i][3]]=rb; } } return cnt; } int main() { //freopen("max.in","r",stdin); //freopen("max.out","w",stdout); cin>>T; while(T--) { bool flag=0; cin>>n>>m; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&p[i][1],&p[i][2],&p[i][3],&p[i][4]); if(p[i][2]!=p[i][4]) { flag=1; } } if(flag) { memset(rem,0,sizeof(rem)); cout<<dfs(0,0)<<"\n"; } else { memset(a,0,sizeof(a)); for(int i=1;i<=m;i++) { a[p[i][1]]=max(a[p[i][1]],p[i][2]); a[p[i][3]]=max(a[p[i][3]],p[i][4]); } int cnt=0; for(int i=1;i<=n;i++) { cnt+=a[i]; } cout<<cnt<<"\n"; } } return 0; }