using System;

using System.Collections.Generic;

using System.IO;

​

public class SearchResult

{

    public double Cost = 0;

    public HashSet<Edge<int>> Route = new HashSet<Edge<int>>();

    public void AddEdge(Edge<int> e)

    {

        this.Route.Add(e);

        this.Cost += e.Weight;

    }

​

    public void RemoveEdge(Edge<int> e)

    {

        this.Route.Remove(e);

        this.Cost -= e.Weight;

    }

}

public class Solution

{

    static void Main(String[] args)

    {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution */

​

        //Read input

        var cases = int.Parse(Console.ReadLine());

        for (int i = 0; i < cases; i++)

        {

            var str = Console.ReadLine();

            var tokens = str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

            var n = int.Parse(tokens[0]);

            var m = int.Parse(tokens[1]);

​

            //Build graph

            //int[,] graphArr = new int[n, n];

            //List<List<Edge<int>>> graphAdj = new List<List<Edge<int>>>();

            //List<Edge<int>> edges = new List<Edge<int>>();

            var graph4 = new Graph<int>();

            int numEdges = m;

            for (int j = 0; j < numEdges; j++)  //O(2|E|) space

            {

                str = Console.ReadLine();

                tokens = str.Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);

                var v1 = int.Parse(tokens[0]);

                var v2 = int.Parse(tokens[1]);

                var d = int.Parse(tokens[2]);

​

                graph4.AddEdge(new Edge<int>(v1, v2, d));

​

                //Graph#3

                //edges.Add(new Edge<int>(v1, v2, d));

​

                //Graph#2 

                /*

                int maxV = Math.Max(v1, v2);

                while (graphAdj.Count < maxV)

                {

                    var list = new List<Edge<int>>();

                    graphAdj.Add(list);

                }

​

                int x = v1 - 1, y = v2 - 1;

                var e = new Edge<int>(x, y, d);

                graphAdj[x].Add(e);

                graphAdj[y].Add(e);*/

​

                //Graph#1                

                //graphArr[x, y] = d;

                //graphArr[y, x] = d;                

            }

​

            //SlowApproach(n, graphAdj);

​

            //Let's create the ultimate spanning tree

            FastApproach(n, graph4);

        }

    }

​

    private static void FastApproach(int n, Graph<int> graph)

    {

        int numVert = 3;

        var mst = KruskalMST(graph);

        SearchResult minResult = null;

        foreach (var v in mst.Vertices.Keys)

        {

            SearchResult result = DFS(mst, v, numVert-1);

            if (minResult==null || result.Cost < minResult.Cost)

            {

                minResult = result;

            }

        }

        Console.WriteLine(minResult.Cost);

    }

​

    private static SearchResult DFS(Graph<int> graph, int v, int edgeCount)

    {

        var path = new SearchResult();

        var bestPath = new SearchResult() { Cost = int.MaxValue };

        DFS(graph, path, bestPath, v, edgeCount);

        return bestPath;

    }

​

    private static void DFS(Graph<int> graph, SearchResult path, SearchResult bestPath, int root, int edgeCount)

    {

        var neighbors = graph.Vertices[root];

        foreach(var e in neighbors)

        {

            if (path.Route.Contains(e)) { continue; }

            bool edgeAdded = false;

            if(e.Source!= root)

            {

                edgeAdded = true;

                path.AddEdge(e);

                --edgeCount;

                if (edgeCount > 0)

                {

                    DFS(graph, path, bestPath, e.Source, edgeCount);

                }

            }

            else if (e.Destination != root)

            {

                edgeAdded = true;

                path.AddEdge(e);

                --edgeCount;

                if (edgeCount > 0)

                {

                    DFS(graph, path, bestPath, e.Destination, edgeCount);

                }

            }

​

            if(edgeCount==0)

            {

                if(path.Cost<bestPath.Cost)

                {

                    bestPath.Route.Clear();

                    bestPath.Cost = 0;

                    foreach(var pe in path.Route)

                    {

                        bestPath.AddEdge(pe);

                    }

                }

            }

​

            if(edgeAdded)

            {

                path.RemoveEdge(e);

                ++edgeCount;

            }

        }

    }

/*

    private static void SlowApproach(int n, List<List<Edge<int>>> graphAdj)

    {

        //For each set of 3 cities, find the minimum spanning tree, store that total distance

        //If that distance is < min, then set that route is min route and save distance as min

        var min = int.MaxValue;

        List<int> route = null;

        foreach (var subset in GetSubsets(n, 3)) //O(2^n) Runtime

        {

            var subGraph = CreateSubGraph(graphAdj, subset);

            var cost = GetMinimumSpanningTree(subGraph);

            if (cost < min)

            {

                min = cost;

                route = subset;

            }

        }

        Console.WriteLine(min);

    }*/

​

    private static Graph<int> CreateSubGraph(List<List<Edge<int>>> graph, List<int> vertexSet)

    {

        Graph<int> g = new Graph<int>();

        foreach (var v in vertexSet)

        {

            var neighbors = graph[v];

            foreach (var edge in neighbors)

            {

                if (vertexSet.Contains(edge.Source) && vertexSet.Contains(edge.Destination))

                {

                    g.AddEdge(edge);

                }

            }

        }

        return g;

    }    

​

    private static IEnumerable<List<int>> GetSubsetsOld(int n, int numElems)

    {

        double rows = Math.Pow(2, n);

        for (int counter = 0; counter < rows; counter++)

        {

            var subset = new List<int>();

            for (var bit = 0; bit < n; bit++)

            {

                var signal = counter & (1 << bit);

                if (signal > 0)

                {

                    if (subset.Count == numElems) { subset.Clear(); break; }

                    subset.Add(bit);

                }

            }

​

            if (subset.Count == numElems)

            {

                yield return subset;

            }

        }

    }

​

    private static IEnumerable<List<int>> GetSubsets(int n, int numElems)

    {

        //First set: 111

        var msb = numElems - 1;

        int initial = InitialSet(numElems);

        yield return Convert(n, numElems, initial);

        int prev = initial;

​

        // Move the 1 bit at msb, to msb + 1 

        /*        

        var source = msb;

        var destination = msb + 1;

        bits = MoveBit(bits, source, destination);

        */

​

​

        // Move the 1 bit at end, to end + 1

        // Now set remaining: 1001, 1011

        int newBits = NewSet(numElems, ref msb);

​

        //bits:1011

        yield return Convert(n, numElems, newBits);

        prev = newBits;

​

        while (msb < n)

        {

            //**************

            //Next set

            //---------------

            // Find the first bit from Right-to-Left set to 1

            int pos = FindNextMSB(prev);

​

            if (pos == msb) //If we've reach our most significant bit, then we can't shift, we have to create a NewSet

            {

                if (msb < n - 1)

                {

                    newBits = NewSet(numElems, ref msb);

                    yield return Convert(n, numElems, newBits);

                    prev = newBits;

                }

                else { //Exit condition: msb==n-1

                    break;

                }

            }

            else //we haven't reached our msb

            {

                var source = pos;

                var dest = pos + 1;

                newBits = MoveBit(prev, source, dest);

                yield return Convert(n, numElems, newBits);

                prev = newBits;

            }

        }

    }

​

    private static int FindNextMSB(int prev)

    {

        var pos = 0;

        while ((prev & 1 << pos) == 0)

        {

            ++pos;

        }

​

        //Now continue until the end consecutive 1's

        ++pos;

        while ((prev & 1 << pos) > 0)

        {

            ++pos;

        }

        //Backup to the last 1 bit in consecutive 1's

        --pos;

        return pos;

    }

​

    private static int NewSet(int numElems, ref int msb)

    {

        var newBits = 1 << ++msb;

        var rem = numElems - 1;

        for (int i = 0; i < rem; i++)

        {

            newBits |= 1 << i;

        }

​

        return newBits;

    }

​

    private static int MoveBit(int orig, int source, int destination)

    {

        var allBitsSet = int.MinValue;

        var rightMask = (1 << source) - 1;

        var leftMask = allBitsSet - (1 << (destination + 1));

        int mask = 0;

        if (destination - source > 1)

        {

            var middleA = (1 << destination) - 1;

            var middleB = (1 << source + 1) - 1;

            var middleMask = middleA - middleB;

            mask = leftMask | middleMask | rightMask;            

        }

        else

        {

            mask = leftMask | rightMask;

        }

        var result = orig & mask;

        result |= 1 << destination;

        return result;

    }

​

    private static int MoveBitOld(int orig, int source, int destination)

    {

        if(source>=destination) { throw new InvalidOperationException("Source must be > Destination"); }

        int result = 0;

        for (int pos = 0; pos <= destination; pos++)

        {            

            if (pos == source)

            {

                ++pos; //don't set the source position bit, because we're moving it

            }

            else if(pos==destination)

            {

                result |= 1 << pos; //set the destination bit, because we're moving it from source

            }

            else //if (pos != source && pos != destination) //Copy

            {

                result |= orig & (1 << pos);

            }

        }

        return result;

    }

​

    private static int InitialSet(int numElems)

    {

        var bits = 0;

        for (int i = 0; i < numElems; i++)

        {

            bits |= 1 << i;

        }

​

        return bits;

    }

​

    private static List<int> Convert(int n, int numElems, int bits)

    {

        var subset = new List<int>();

        for (var bit = 0; bit < n; bit++)

        {

            var signal = bits & (1 << bit);

            if (signal > 0)

            {                

                subset.Add(bit);

                if (subset.Count == numElems) { break; }

            }            

        }

        return subset;

    }

​

    /*

    private static IEnumerable<List<int>> GetSubsets2(int n, int numElems)

    {

        var list = new List<int>();

        for (int i = 0; i < n; i++) {

            list.Add(i);

        }

        var size = list.Count;

        var result = GetCombinations(list, 0, numElems, size);

        return result;

    }

​

    private static List<List<int>> GetCombinations(List<int> s, int current, int numElems, int size)

    {

        var allSets = new List<List<int>>();

        if (current == size)

        {

            allSets.Add(new List<int>()); return allSets;

        }

        var item = s[0];

        var rem = Subset(s, 1);

        var sets = GetCombinations(rem, current + 1, numElems, size);

        allSets.AddRange(sets);

        foreach (var set in sets)

        {

            if (set.Count == numElems) { continue; }

            var newSet = new List<int>();

            newSet.AddRange(set);

            newSet.Insert(0, item);

            allSets.Add(newSet);

        }

        return allSets;

    }

​

    private static List<int> Subset(List<int> s, int start)

    {

        var newList = new List<int>();

        for(int i= start; i<s.Count; i++)

        {

            newList.Add(s[i]);

        }

        return newList;

    }

​

    private List<string> GetCombinations(string s, int numElems)

    {

        return GetCombos(s, 0, numElems);

    }

​

    private List<string> GetCombos(string s, int current, int numElems)

    {

        var allSets = new List<string>();

        if (current == numElems) { allSets.Add(string.Empty); return allSets; }

        var item = s[0].ToString();

        var subStr = s.Substring(1);

        var sets = GetCombos(subStr, current + 1, numElems);

        if (current == numElems) { return sets; }

        foreach (var set in sets)

        {

            var newSet = set.Insert(0,item);

            allSets.Add(newSet);

        }

        return allSets;

    }

​

​

    private List<string> GetPermutations(string s)

    {

        return GetPerms(s, 0, s.Length);

    }

​

    private List<string> GetPerms(string s, int current, int numElems)

    {

        var allSets = new List<string>();

        if(current==numElems) { allSets.Add(string.Empty); return allSets; }

        var item = s[0].ToString();

        var subStr = s.Substring(1);

        var sets = GetPerms(subStr, current + 1, numElems);

        foreach(var set in sets)

        {            

            for(int i=0; i<=set.Length; i++)

            {                

                var newSet = set.Insert(i, item);

                allSets.Add(newSet);

            }

        }

        return allSets;

    }

    */

    private static int GetMinimumSpanningTree(Graph<int> graph)

    {

        var result = KruskalMST(graph);

        int cost = 0;

        foreach (var e in result.Edges)

        {

            cost += e.Weight;

        }

        return cost;

    }

​

    private static /*List<Edge<int>>*/Graph<int> KruskalMST(Graph<int> graph)

    {

        int numVert = graph.NumVertices;

        //List<Edge<int>> result = new List<Edge<int>>();

        Graph<int> resultGraph = new Graph<int>();

        int i = 0; // iterator for sorted edges

​

        //Sort edges

        var edges = new List<Edge<int>>();

        foreach (var edge in graph.Edges)

        {

            edges.Add(edge);

        }

        edges.Sort();

​

        //Create a unique subset for each vertex

        var subsets = new Dictionary<int, Subset>();

        foreach (int v in graph.Vertices.Keys)

        {

            subsets.Add(v, new Subset(v, 0));

        }

​

        //while (result.Count < (numVert - 1))

        while(resultGraph.Edges.Count < (numVert-1))

        {

            //Pick the smallest edge

            var nextEdge = edges[i++];

            int x = Find(subsets, nextEdge.Source);

            int y = Find(subsets, nextEdge.Destination);

​

            if (x != y)

            {

                //result.Add(nextEdge);

                resultGraph.AddEdge(nextEdge);

                Union(subsets, x, y);

            }

        }

        //return result;

        return resultGraph;

    }

​

    private static int Find(Dictionary<int, Subset> subsets, int i)

    {

        if (subsets[i].Parent != i)

            subsets[i].Parent = Find(subsets, subsets[i].Parent);

​

        return subsets[i].Parent;

    }

​

    private static void Union(Dictionary<int, Subset> subsets, int x, int y)

    {

        int xroot = Find(subsets, x);

        int yroot = Find(subsets, y);

​

        // Attach smaller rank tree under root of high rank tree

        // (Union by Rank)

        if (subsets[xroot].Rank < subsets[yroot].Rank)

        {

            subsets[xroot].Parent = yroot;

        }

        else if (subsets[xroot].Rank > subsets[yroot].Rank)

        {

            subsets[yroot].Parent = xroot;

        }

​

        // If ranks are same, then make one as root and increment

        // its rank by one

        else

        {

            subsets[yroot].Parent = xroot;

            subsets[xroot].Rank++;

        }

    }

}

​

public class Tree<T>

{

    public TreeNode<T> Root;

}

​

public class TreeNode<T>

{

    public TreeNode(T val) { this.Value = val; }

    public T Value;

}

​

public class Graph<T>

{

    public int NumVertices { get { return this.Vertices.Count; } }

    public int NumEdges { get { return this.Edges.Count; } }

    public HashSet<Edge<T>> Edges = new HashSet<Edge<T>>();

    public Dictionary<T,List<Edge<T>>> Vertices = new Dictionary<T,List<Edge<T>>>();

​

    public void AddEdge(Edge<T> edge)

    {

        if (!this.Edges.Contains(edge))

        {

            this.Edges.Add(edge);

            AddEdge(edge.Source, edge);

            AddEdge(edge.Destination, edge);

        }

    }

​

    private void AddEdge(T key, Edge<T> edge)

    {

        List<Edge<T>> list;

        if (!this.Vertices.ContainsKey(key))

        {

            list = new List<Edge<T>>();

            this.Vertices.Add(key, list);

        }

        else

        {

            list = this.Vertices[key];

        }

        list.Add(edge);

    }

}

​

public class Subset

{

    public Subset(int parent, int rank) { this.Parent = parent; this.Rank = rank; }

    public int Parent;

    public int Rank;

}

​

public class Edge<T> : IComparable<Edge<T>>

{

    public Edge(T v1, T v2, int weight)

    {

        this.Source = v1;

        this.Destination = v2;

        this.Weight = weight;

    }

​

    public T Source;

    public T Destination;

    public int Weight;

​

    public int CompareTo(Edge<T> other)

    {

        return Convert.ToInt32(this.Weight).CompareTo(Convert.ToInt32(other.Weight));

    }

}