#include <bits/stdc++.h> #define int long long using namespace std; int t; int n,m; struct node{ int x,y,c,d; }a[100005]; int p[100005],s[100005]; int ans=0; int h[100005]; int cz[100005]; int bp[100005]; bool cmp(node x,node y){ return x.c+x.d<y.c+y.d; } void dfs(int dq){ if (dq==m+1){ for (int i=1;i<=m;i++){ h[a[cz[i]].x]=a[cz[i]].c; h[a[cz[i]].y]=a[cz[i]].d; // cout<<cz[i]<<" "; } int lans=0; for (int i=1;i<=n;i++){ lans+=h[i]; } ans=max(ans,lans); } for (int i=1;i<=m;i++){ if (bp[i]==0){ bp[i]=1; cz[dq]=i; dfs(dq+1); bp[i]=0; } } } signed main(){ scanf("%lld",&t); while (t--){ int sdf=0; scanf("%lld%lld",&n,&m); for (int i=1;i<=m;i++){ scanf("%lld%lld%lld%lld",&a[i].x,&a[i].c,&a[i].y,&a[i].d); if (a[i].c!=a[i].d) sdf++; // p[i]=i; } memset(h,0,sizeof(h)); ans=0; if (sdf==0){ sort(a+1,a+m+1,cmp); for (int i=1;i<=m;i++){ h[a[i].x]=a[i].c; h[a[i].y]=a[i].d; } for (int i=1;i<=n;i++){ ans+=h[i]; } cout<<ans<<endl; } else{ dfs(1); printf("%lld\n",ans); } } return 0; }