/*

 问题

 输入顶点数p和边数q以及q条边

 计算并输出顶点1到每个顶点的最短路径花费，再加上每个顶点到1的最短路径花费

 解题思路

 求1号顶点到其余顶点的最短路径之和不难，Dijkstra求解单源最短路即可，关键是其余顶点到1号顶点的最短路径之和

 具体做法是将原图的所有边都反向存储一遍，再跑一边1号顶点到其余顶点的Dijkstra单源最短路就是要求的其余顶点到1号顶

 点的最短路径之和。

 另外由于顶点和边很多，所以采用邻接表+优先队列优化的Dijkstra算法。

 */

 #include<bits/stdc++.h>//HDU G++

 const int maxn=1e6+;

 const int INF=1e9+;

 using namespace std;

 int u[maxn],v[maxn],w[maxn]; 

 struct Edge{

     int from,to,dist;

 }; 

 struct HeapNode{

     int d,u;

     bool operator < (const HeapNode& rhs) const {//优先队列，重载<运算符

         return d >rhs.d;

     }

 };

 struct Dijkstra{

     int n,m;

     vector<Edge> edges;  //邻接表

     vector<int> G[maxn]; //每个节点出发的边编号（从0开始编号）

     bool done[maxn];     //是否已经永久编号

     int d[maxn];         //s到各个点的距离

     int p[maxn];         //最短路中的上一条边 

     void init(int n){

         this->n =n;

         for(int i=;i<n;i++)    G[i].clear();//清空邻接表

         edges.clear();                         //清空边表

     }

     void AddEdge(int from,int to,int dist){

         //如果是无向图需要将每条无向边存储两边，及调用两次AddEdge

         edges.push_back((Edge){from,to,dist});

         m=edges.size();

         G[from].push_back(m-);

     }

     void dijkstra(int s){//求s到其他点的距离

         priority_queue<HeapNode> Q;

         for(int i=;i<n;i++)    d[i]=INF;

         d[s]=;

         memset(done,,sizeof(done));

         Q.push((HeapNode){,s});

         while(!Q.empty()){

             HeapNode x =Q.top();

             Q.pop();

             int u=x.u;

             if(done[u]) continue;

             done[u]=true;

             for(int i=;i<G[u].size();i++){

                 Edge& e = edges[G[u][i]];

                 if(d[e.to] > d[u] + e.dist){

                     d[e.to] = d[u] + e.dist;

                     p[e.to] = G[u][i];

                     Q.push((HeapNode){d[e.to],e.to});

                 }

             }

         }

     }

 };

 struct Dijkstra solver;

 int main()

 {

     int T,n,m;

     scanf("%d",&T);

     while(T--){

         scanf("%d%d",&n,&m);

         solver.init(n);

         for(int i=;i<=m;i++){

             scanf("%d%d%d",&u[i],&v[i],&w[i]);

             u[i]--;//模板中的顶点从0开始

             v[i]--;

             solver.AddEdge(u[i],v[i],w[i]);

         }

         solver.dijkstra();

         int ans=;

         for(int i=;i<solver.n;i++)

             ans += solver.d[i];

         solver.init(n);

         for(int i=;i<=m;i++){

             solver.AddEdge(v[i],u[i],w[i]);//清空后反向存储

         }

         solver.dijkstra();

         for(int i=;i<solver.n;i++)

             ans += solver.d[i];

         printf("%d\n",ans);

     }

     return ;

 }