#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie
{
    int i, j, c;
};

int n, m,
    cost;       ///costul APM
muchie M[400001];
int CC[200001];    ///CC[i] == c.c. (subarborele) din care face parte nodul i
bool S[400001];   ///S[i] = 1 <==> muchia i a fost selectata in APM

void citire()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
        fin >> M[i].i >> M[i].j >> M[i].c;
}

void afis()
{
    fout << cost << '\n' << m << '\n';
    for(int i = 1; i <= m; i++)
        if(S[i] == 1)
            fout << M[i].i << ' ' << M[i].j << '\n';
}

bool comp(const muchie &a, const muchie &b)
{
    return a.c < b.c;
}

void Kruskal()
{
    sort(M + 1, M + m + 1, comp);
    for(int i = 1; i <= n; i++)
        CC[i] = i; ///fiecare nod constituie o c.c.
    //
    int k = 1; ///incepem cu prima muchie
    for(int l = 1; l < n; l++)
    {
        while(CC[M[k].i] == CC[M[k].j]) ///cautam o muchie ale carei capete sunt din cc diferite
            k++;
        S[k] = 1; ///marcam selectarea muchiei k
        cost += M[k].c;
        int ccj = CC[M[k].j]; ///unificam cc ale lui i si j
        for(int i = 1; i <= n; i++)
            if(CC[i] == ccj)
                CC[i] = CC[M[k].i];
    }
}

int main()
{
    citire();
    Kruskal();
    afis();
    fin.close();
    fout.close();
    return 0;
}