#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define cost first

using namespace std;

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

pair <int, pair <int, int> > muchie[10003], apm[105];
vector <int> T,H;

int radacina(int k)
{
    while(T[k]!=0)
    {
        k=T[k];
    }
    return k;
}

int main()
{
    int n,m,x,y,c,i,j,k,v1,v2,scost=0,r1,r2;
    in >> n >> m;
    for(i=1;i<=m;i++)
    {
        in >> x >> y >> c;
        muchie[i].cost=c;
        muchie[i].second.first=x;
        muchie[i].second.second=y;
    }
    sort(muchie+1,muchie+m+1);
    /*for(i=1;i<=m;i++)
    {
        cout << muchie[i].cost << ' ' << muchie[i].second.first << ' ' << muchie[i].second.second << '\n';
    }
    cout << "\n\n";*/
    for(i=0;i<=n;i++)
    {
        T.push_back(0);
        H.push_back(0);
    }
    k=1;
    for(i=1;i<=m;i++)
    {
        v1=muchie[i].second.first;
        v2=muchie[i].second.second;
        //cout << v1 << ' ' << v2 << '\n';
        r1=radacina(v1);
        r2=radacina(v2);
        if(r1!=r2)
        {
            apm[k++]=muchie[i];
            scost+=muchie[i].cost;
            if(k==n)
            {
                break;
            }
            if(H[r1]>H[r2])
            {
                T[r2]=r1;
            }
            else
            {
                if(H[r2]>H[r1])
                {
                    T[r1]=r2;
                }
                else
                {
                    T[r2]=r1;
                    H[r1]++;
                }
            }
        }
    }
    out << scost << '\n';
    out << n-1 << '\n';
    for(i=1;i<n;i++)
    {
        out << apm[i].second.first << ' ' << apm[i].second.second << '\n';

    }
}