#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define mp make_pair
#define rep( i , a , b ) for( int i = (a) , i##end = b ; i <= i##end ; ++ i )
#define per( i , a , b ) for( int i = (a) , i##end = b ; i >= i##end ; -- i )
#define mem( a ) memset( a , 0 , sizeof (a) )
#define all( x ) x.begin() , x.end()
//#define int long long
typedef long long ll;
const int MAXN = 2e5 + 10;
int n , m;

unordered_map<int,int> M;
int bc[23000];
int cur; int st , idx;
void dfs( int t ) {
	if( t == n + 1 ) {
		++ idx;
		M[cur] = idx;
		bc[idx] = cur;
		return;
	}
	cur = cur * 10 + st + 1 , ++ st;
	dfs( t + 1 );
	cur /= 10 , -- st;
	rep( i , 1 , st ) {
		cur = cur * 10 + i;
		dfs( t + 1 );
		cur /= 10;
	}
}

struct ed {
	int u , v , w , tim;
	
} E[MAXN] ;

int G[11][11][2];
int dp[62][23000][32];

ll p10[10];
int gd( int s , int t ) {
	return s / p10[t - 1] % 10;
}

int mk( int s , int u , int t ) {
	int ar = 0;
	per( i , n , 1 ) {
		int p = gd( s , i );
		ar = ar * 10 + ( p == u ? t : p > u ? p - 1 : p );
	}
	return ar;
}

void ck( int& a , const int& b ) {
	a = max( a , b );
}

void solve() {
	cin >> n >> m;
	idx = 0;
	dfs( 1 );
//	cout << M.size() << endl;
	rep( u , 1 , n ) rep( v , 1 , n ) rep( t , 0 , 1 ) G[u][v][t] = 0;
	rep( i , 1 , m ) {
		int u , v , a , b;
		scanf("%d%d%d%d",&u,&v,&a,&b);
		G[u][v][1] = a , G[u][v][0] = b;
		if( a < b ) E[i * 2 - 1] = (ed) { u , v , 1 , 0 } , E[i * 2] = (ed) { u , v , 0 , 1 };
		else E[i * 2 - 1] = (ed) { u , v , 1 , 1 } , E[i * 2] = (ed) { u , v , 0 , 0 };
	}
	sort( E + 1 , E + 2 * m + 1 , [&]( ed a , ed b ) { return G[a.u][a.v][a.w] < G[b.u][b.v][b.w]; } );
	rep( i , 0 , m * 2 ) rep( s , 0 , idx ) rep( j , 0 , m ) dp[i][s][j] = -0x3f3f3f3f;
	dp[0][1][0] = 0;
	rep( i , 1 , m * 2 ) {
		int u = E[i].u , v = E[i].v;
		rep( s , 1 , idx ) rep( j , 0 , m ) if( dp[i - 1][s][j] >= 0 ) {
			int sta = bc[s];
			int fu = gd( sta , u ) , fv = gd( sta , v );
			if( fu == fv ) {
				if( E[i].tim == 0 ) {
					ck( dp[i][s][j] , dp[i - 1][s][j] );
					ck( dp[i][s][j + 1] , dp[i - 1][s][j] );
				} else {
					ck( dp[i][s][j] , dp[i - 1][s][j] );
				}
			} else {
				int t = min( fu , fv );
				int tas = mk( sta , fu == t ? fv : fu , t ) , S = M[tas];
				if( E[i].tim == 0 ) {
					ck( dp[i][S][j + E[i].w] , dp[i - 1][s][j] + G[u][v][E[i].w] );
					ck( dp[i][s][j + !E[i].w] , dp[i - 1][s][j] );
				} else {
					ck( dp[i][S][j] , dp[i - 1][s][j] + G[u][v][E[i].w] );
				}
			}
//			cout << i - 1 << ' ' << bc[s] << ' ' << j << ' ' << dp[i - 1][s][j] << endl;
		}
	}
	rep( k , 0 , m ) {
		printf("%d\n",dp[m * 2][M[( p10[n] - 1 ) / 9]][k]);
	}
}

signed main() {
	p10[0] = 1;
	rep( i , 1 , 10 ) p10[i] = p10[i - 1] * 10;
//	freopen("in","r",stdin);
//	freopen("out","w",stdout);
	int T;cin >> T;while( T-- ) solve();
//	solve();
}