#include <bits/stdc++.h>

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

// const int minimum = -1001;

struct edgeTree
{
    int cost, nodeA, nodeB;
    bool operator>(const edgeTree& other) const
    {
        return cost > other.cost; 
    }
};

struct dsu
{
    std::vector<int> parent, rank;

    dsu(int n) // initialize
    {
        parent.resize(n + 1);
        rank.assign(n + 1, 0);

        for (int i = 1; i <=n ; i ++) parent[i] = i;
    }

    int findRoot(int x)
    {
        if (parent[x] == x) return x;
        return findRoot(parent[x]);
    }

    bool unite(int a, int b)
    {
        a = findRoot(a);
        b = findRoot(b);
    
        if (a == b) return false; // same component

        if (rank[a] < rank[b]) std::swap(a,b);
        parent[b] = a;
        if (rank[a] == rank[b]) rank[a] += 1;
        return true;
    }

};

void kruskal(int numNodes)
{
    int numEdges, a,b,c, numVisited = 0, cost = 0;
    // std::vector<char> visited(numNodes + 1, false);
    std::priority_queue<edgeTree, std::vector<edgeTree>, std::greater<edgeTree>> pq;
    std::vector<std::pair<int, int>> tree;

    fin>>numEdges;
    for (int i = 0 ; i < numEdges; i ++)
    {
        fin>>a>>b>>c;
        pq.push({c,a,b});        
    }

    dsu dsuController(numNodes);

    while (!pq.empty() && numVisited <= numNodes)
    {
        edgeTree curr = pq.top();
        if (dsuController.unite(curr.nodeA, curr.nodeB)) // at least one new vertex
        {
            cost += curr.cost;
            tree.push_back({curr.nodeA, curr.nodeB});
        }
        pq.pop();
    }

    fout<<cost<<'\n'<<tree.size()<<'\n';
    for (size_t index = 0 ; index < tree.size(); index++)
        fout<<tree[index].first<<' '<<tree[index].second<<'\n';

}

int main()
{
    int numNodes;

    fin>>numNodes;
    kruskal(numNodes);

    return 0;
}