#include <iostream>
#include <fstream>

using namespace std;

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

struct muchii
{
    int nod1, nod2, cost;
}v[400005], aux;

int n, m, x, y, nr, suma;
int N[400005], a[400005][400005];

int parinte(int a){
    if(N[a]==a)
        return a;
    N[a]=parinte(N[a]);
    return N[a];
}

void unire(int a, int b)
{
    int tata_a, tata_b;
    tata_a = parinte(a);
    tata_b = parinte(b);
    N[tata_a] = tata_b;
}

int main()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++){
        fin>>v[i].nod1>>v[i].nod2>>v[i].cost;
    }
    for (int i=1; i<m; i++)
        for (int j=i+1; j<=m; j++)
        if (v[i].cost>v[j].cost){
            aux=v[i];
            v[i]=v[j];
            v[j]=aux;
        }
    for (int i=1; i<=n; i++)
        N[i]=i;
    while (nr<n-2)
    {
        for (int i=1; i<=m; i++){
            if (parinte(v[i].nod1)!=parinte(v[i].nod2)){
                suma+=v[i].cost;
                nr++;
                unire(v[i].nod1, v[i].nod2);
                a[v[i].nod1][v[i].nod2]=a[v[i].nod2][v[i].nod1]=1;
            }
        }
    }
    fout<<suma<<"\n";
    fout<<nr<<"\n";
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            if (a[i][j]==1){
                a[i][j]=a[j][i]=0;
                fout<<i<<" "<<j<<"\n";
            }
    return 0;
}