#include <fstream>
#include <vector>
#include <climits>
#include <utility>
#include <deque>

struct Pair
{
    int a, b;
    Pair(int c, int d) : a(c), b(d) {}
};

struct Edge
{
	int v;
	int weight;
	Edge() : v(), weight() {}
	Edge(int a, int b) : v(a), weight(b) {}
};

struct Vertex
{
	int u;
	std::vector<Edge> myV;
	Vertex() : u(), myV() {}
};

void prim(Vertex *A, int nV, long long &sum, std::deque<Pair> &myDeq);
void upheap(long long *dist, int *poz, int *heap, int j);
void downheap(long long *dist, int *poz, int *heap, int &size, int j);
int pop(long long *dist, int *poz, int *heap, int &size);

int main()
{
    std::ifstream in("apm.in");
    std::ofstream out("apm.out");
    int nV, nE, a, b, c;
    in >> nV >> nE;
    Vertex *A = new Vertex[nV + 1];
    for(int i = 1; i <= nV; i++)
        A[i].u = i;
    for(int i = 0; i < nE; i++)
        in >> a >> b >> c, A[a].myV.push_back(Edge(b, c)),
            A[b].myV.push_back(Edge(a, c));
    long long sum;
    std::deque<Pair> myDeq;
    prim(A, nV, sum, myDeq);

    out << sum << '\n' << myDeq.size() << '\n';

    while(!myDeq.empty())
    {
        Pair aux = myDeq.front();
        myDeq.pop_front();
        out << aux.a << ' ' << aux.b << '\n';
    }

	return 0;
}

void upheap(long long *dist, int *poz, int *heap, int j)
{
    if(j == 1) return;
    int par = j / 2;
    if(dist[heap[j]] < dist[heap[par]])
    {
        poz[heap[j]] = par;
        poz[heap[par]] = j;
        std::swap(heap[j], heap[par]);
        upheap(dist, poz, heap, par);
    }
}

void downheap(long long *dist, int *poz, int *heap, int &size, int j)
{
    int l = 2 * j, r = 2 * j + 1, par = j;
    if(l <= size && dist[heap[l]] < dist[heap[par]]) par = l;
    if(r <= size && dist[heap[r]] < dist[heap[par]]) par = r;
    if(par != j)
    {
        poz[heap[par]] = j;
        poz[heap[j]] = par;
        std::swap(heap[j], heap[par]);
        downheap(dist, poz, heap, size, par);
    }
}

int pop(long long *dist, int *poz, int *heap, int &size)
{
    poz[heap[1]] = size;
    poz[heap[size]] = 1;
    std::swap(heap[1], heap[size]);
    size--;
    downheap(dist, poz, heap, size, 1);
    return heap[size + 1];
}

void prim(Vertex *A, int nV, long long &sum, std::deque<Pair> &myDeq)
{
	long long *dist = new long long[nV + 1];
	bool *check = new bool[nV + 1];
	int *parent = new int[nV + 1], *poz = new int[nV + 1],
            *heap = new int[nV + 1];
	int size = nV;
	for(int i = 1; i <= nV; i++)
		dist[i] = INT_MAX, check[i] = false, parent[i] = -1,
            poz[i] = i, heap[i] = i;
    dist[1] = 0;
    check[1] = true;
    parent[1] = -1;
    sum = 0;
    while(size != 0)
    {
        int aux = pop(dist, poz, heap, size);
        check[aux] = true;
        if(parent[aux] != -1)
        {
            sum += dist[aux];
            myDeq.push_back(Pair(parent[aux], aux));
        }
        for(unsigned i = 0; i < A[aux].myV.size(); i++)
        {
            int y = A[aux].myV[i].v;
            if(check[y]) continue;
            long long alt = A[aux].myV[i].weight;
            if(alt < dist[y])
            {
                parent[y] = aux;
                dist[y] = alt;
                upheap(dist, poz, heap, poz[y]);
            }
        }
    }
}