CSTREET_Cobbled_streets

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import static java.lang.Integer.parseInt;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader reader;
    static int price, n_buildings, m_streets;
    static ArrayList<pair> graph[];
    static boolean visited[];
    static PriorityQueue<pair> q;
    static long cost;

    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        int tc = parseInt(reader.readLine());
        for (int t = 0; t < tc; t++) {
            Input();
            process();
        }

    }

    public static void Input() throws IOException {

        StringTokenizer tok;
        price = parseInt(reader.readLine());
        n_buildings = parseInt(reader.readLine());
        m_streets = parseInt(reader.readLine());
        graph = new ArrayList[n_buildings + 1];
        for (int i = 1; i <= n_buildings; i++) {
            graph[i] = new ArrayList<pair>();
        }
        for (int i = 0; i < m_streets; i++) {
            tok = new StringTokenizer(reader.readLine());
            int node1 = parseInt(tok.nextToken()), node2 = parseInt(tok.nextToken()), cost = parseInt(tok.nextToken());
            graph[node1].add(new pair(node2, cost));
            graph[node2].add(new pair(node1, cost));
        }

    }

    public static void process() {
        visited = new boolean[n_buildings + 1];
        q = new PriorityQueue<pair>(Comparator.comparing((pair obj) -> obj.cost));
        q.add(new pair(1, 0));
        cost = 0;
        while (!q.isEmpty()) {
            pair obj = q.poll();
            if (!visited[obj.node]) {
                visited[obj.node] = true;
                cost += obj.cost;
            }
            for (pair i : graph[obj.node]) {
                if (!visited[i.node]) {
                    q.add(i);
                }
            }
        }
        System.out.println(price * cost);

    }

    static class pair {

        int node, cost;

        public pair(int node, int cost) {
            this.node = node;
            this.cost = cost;
        }

    }
}