#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int e1, e2, cost;
};
muchie G[400001];
int  cc[200001], nrm[200000];
int n, m,costapm;
void init()
{
    f >> n >> m;
    for(int i = 1; i <= m; i++)
        f >> G[i].e1 >> G[i].e2 >> G[i].cost;
}
bool comp(const muchie &A, const muchie &B)
{
    return A.cost < B.cost;
}
void afisare()
{
    g << costapm << '\n' << n - 1 << '\n';
    for(int i = 1; i < n; i++)
        g << G[nrm[i]].e1 << ' ' << G[nrm[i]].e2 << '\n';
}
int Find(int i)
{
    if(cc[i] == 0)
        return i;
    cc[i] = Find(cc[i]);
    return cc[i];
}
void kruskal()
{
    int nm = 0;
    for(int i = 1; i <= m; i++)
    {
        int c1 = Find(G[i].e1);
        int c2 = Find(G[i].e2);
        if(c1 != c2)
        {
            costapm += G[i].cost;
            cc[c1] = c2; // reuniune
            nrm[++nm] = i;
            if(nm == n - 1)
                break;
        }
    }
}

int main()
{
    init();
    sort(G + 1, G + m + 1, comp);
    kruskal();
    afisare();
    return 0;
}