#include <fstream>

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

const int maxN = 200001;
const int maxM = 400001;

int N, M;

struct disjoint_set {
    int parent;
    int rank_ = 0;
}V[maxN];

int rootOf(int i)
{
    if(V[i].parent != i)
    {
        V[V[i].parent].parent = rootOf(V[i].parent);
        V[i].parent = V[V[i].parent].parent;
    }
    return V[i].parent;
}

void unify(int i, int j)
{
    int root1 = rootOf(i);
    int root2 = rootOf(j);

    if(V[root1].rank_ > V[root2].rank_)
    {
        int swap_ = root1;
        root1 = root2;
        root2 = swap_;
    }
    V[root1].parent = root2;
    if(V[root1].rank_ == V[root2].rank_)
        V[root2].rank_++;
}

struct edge{
    int v1, v2;
    int cost;
    bool chosen = false;
}E[maxM], support[maxM];

bool compareEdges(edge e, edge f)
{
    return true;

    if(e.cost <= f.cost)
        return true;
    return false;
}

void mergeSort(int i, int j)
{
    if(i >= j)
        return;
    int m = (i+j)/2;
    mergeSort(i, m);
    mergeSort(m+1, j);

    int k = i, w = m+1, u = i;
    while(k <= m && w <= j)
    {
        if(E[k].cost < E[w].cost)
            support[u++] = E[k++];
        else
            support[u++] = E[w++];
    }
    while(k <= m)
        support[u++] = E[k++];
    while(w <= j)
        support[u++] = E[w++];
    for(int h = i; h <= j; h++)
     E[h] = support[h];
}

int main()
{
    fin >> N >> M;

    for(int i=1; i<=N; i++)
        V[i].parent = i;

    for(int i=1; i<=M; i++)
    {
        int X, Y, C;
        fin >> X >> Y >> C;
        E[i].v1 = X;
        E[i].v2 = Y;
        E[i].cost = C;
    }

    mergeSort(1,M);

    int total_cost = 0;
    for(int i=1; i<=M; i++)
    {
        if(rootOf(E[i].v1) != rootOf(E[i].v2))
        {
            E[i].chosen = true;
            total_cost += E[i].cost;
            unify(E[i].v1, E[i].v2);
        }
    }

    fout << total_cost << '\n' << N-1 << '\n';

    for(int i=1; i<=M; i++)
    {
        if(E[i].chosen)
            fout << E[i].v1 << ' ' << E[i].v2 << '\n';
    }

	fin.close();
	fout.close();
	return 0;
}