using System;

using System.Collections.Generic;

using System.IO;

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>>();

            int numEdges = m;

            for (int j = 0; j < numEdges; j++)

            {

                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]);

​

​

                //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;                

            }

​

            //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))

            {

                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))

                {

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

                    {

                        g.Edges.Add(edge);

                        if (!g.Vertices.Contains(edge.Source))

                        {

                            g.Vertices.Add(edge.Source);

                        }

                        if (!g.Vertices.Contains(edge.Destination))

                        {

                            g.Vertices.Add(edge.Destination);

                        }

                    }

                }

            }

        }

        return g;

    }

​

    private static IEnumerable<List<int>> GetSubsets(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 int GetMinimumSpanningTree(Graph<int> graph)

    {

        var result = KruskalMST(graph);

        int cost = 0;

        foreach (var e in result)

        {

            cost += e.Weight;

        }

        return cost;

    }

​

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

    {

        int numVert = graph.NumVertices;

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

        int i = 0; // iterator for sorted edges

        int e = 0; // iterator for result

​

        //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)

        {

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

        }

​

        while (result.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);

                Union(subsets, x, y);

            }

        }

        return result;

    }

​

    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 HashSet<T> Vertices = new HashSet<T>();

}

​

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));

    }

}