#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <utility>
using namespace std;

vector < vector <int> > muchii;
vector < pair <int, int>> muchii_selectate;
int n, m;
int tati[100];
int viz[100];
int cost=0;

bool comp(vector <int> a, vector <int> b)
{
    return a[2]<b[2];
}

void citire()
{
    ifstream fin("apm.in");
    fin>>n;
    fin>>m;
    for (int i=0; i<m; i++)
    {
        vector <int> v;
        int p;
        fin>>p;
        p--;
        v.push_back(p);
        fin>>p;
        p--;
        v.push_back(p);
        fin>>p;
        v.push_back(p);
        muchii.push_back(v);
    }
}

int root(int nod, int &dist)
{
    while (tati[nod]!=nod)
    {
        nod=tati[nod];
        dist++;
    }
    return nod;
}

void kruskal()
{
    for (int i=0; i<n; i++)
    {
        tati[i]=i;
    }
    int k=0, i=0;
    while (k<n-1)
    {
        int d1=0, d2=0;
        int r1=root(muchii[i][0], d1);
        int r2=root(muchii[i][1], d2);
        if (r1!=r2)
        {
            k++;
            pair <int, int> temp;
            muchii_selectate.push_back(make_pair(muchii[i][0]+1, muchii[i][1]+1));
            cost+=muchii[i][2];
            //cout<<muchii[i][0]+1<<" "<<muchii[i][1]+1<<endl;
            if (d1>d2) tati[r2]=r1;
            else tati[r1]=r2;
        } i++;
    }
}



int main()
{
    citire();
    sort(muchii.begin(), muchii.end(), comp);
    kruskal();
    ofstream fout("apm.out");
    fout<<cost<<endl;
    fout<<n-1<<endl;
    for (int i=0; i<n-1; i++) {
        fout<<muchii_selectate[i].first<<" "<<muchii_selectate[i].second<<endl;
    }
    return 0;
}