#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 101

using namespace std;
struct muchie
{
    int cost;
    int v1, v2;
};
vector <muchie> graf, apm;
bool selectat[nmax];
ifstream f("apm.in");
ofstream g("apm.out");
int n,m,costapm;

int fcomp(muchie a, muchie b)
{
    if (a.cost < b.cost)  //return a.cost < b.cost;
        return 1;
    return 0;
}

int main()
{

    int ct=1;
    f >> n >> m;
    for (int i=0;i<m;i++)
    {
        muchie aux;
        f >> aux.v1 >> aux.v2 >> aux.cost;
        graf.push_back(aux);
    }
    sort(graf.begin(),graf.end(),fcomp);

    selectat[graf[0].v1]=true;
    selectat[graf[0].v2]=true;
    apm.push_back(graf[0]);

    while (apm.size() != n-1)
        for (int i=1;i<m;i++)
        {
            int nod1 = graf[i].v1;
            int nod2 = graf[i].v2;
            if (selectat[nod1]!=selectat[nod2])
            {
                apm.push_back(graf[i]);
                selectat[graf[i].v1]=true;
                selectat[graf[i].v2]=true;
                ct++;
            }

        }

    for (int i=0;i<apm.size();i++)
    {

        costapm += apm[i].cost;
    }
    g<<costapm<<endl<<ct<<endl;
    for(int i=0;i<apm.size();i++)
    {
        g<<apm[i].v1<<" "<<apm[i].v2<<endl;
    }
    return 0;
}