#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 1000001;
const int INFINITE = 0x7f7f7f7f;
class Edge
{
public:
	int v, w;
public:
	Edge()
	{
	}
	Edge( int a, int b )
	{
		v = a;
		w = b;
	}
};

class Graph
{
public:
	vector <Edge> adj[N];
public:
	void clear( int n )
	{
		for( int i = 1; i <= n; i++ )
			adj[i].clear();
	}

	void addedge( int s, int t, int w )
	{
		adj[s].push_back( Edge( t, w ) );
	}
};

int n, m;
__int64 dist[N];
bool used[N];
Graph original, reserse;
queue <int> q;

__int64 spfa( Graph *g )
{
	for( int k = 1; k <= n; k++ )
	{
		used[k] = false;
		dist[k] = INFINITE;
	}

	dist[1] = 0;
	used[1] = true;
	q.push( 1 );

	while( !q.empty() )
	{
		int u = q.front();
		q.pop();
		used[u] = false;

		for( int i = 0; i < g->adj[u].size(); i++ )
		{
			Edge e = g->adj[u].at( i );
			if( dist[u] + e.w < dist[e.v] )
			{
				dist[e.v] = dist[u] + e.w;
				if( !used[e.v] )
				{
					used[e.v] = true;
					q.push( e.v );
				}
			}
		}
	}

	__int64 sum = 0;
	for( int j = 2; j <= n; j++ )
		sum += dist[j];

	return sum;
}

int main()
{
	int t, from, to, w;
//	freopen( "1511.txt", "r", stdin );
	for( scanf( "%d", &t ); t > 0; t-- )
	{
		scanf( "%d%d", &n, &m );
		for( int i = 0; i < m; i++ )
		{
			scanf( "%d%d%d", &from, &to, &w );
			original.addedge( from, to, w );
			reserse.addedge( to, from, w );
		}

		printf( "%I64d\n", spfa( &original ) + spfa( &reserse ) );
		original.clear( n );
		reserse.clear( n );
	}

	return 0;
}