//#include <iostream>
#include<fstream>
#include<vector>
#include<cassert>
#include<algorithm>
//#include<stdio.h>
#define mx 400000
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<int> v[mx], vect1[mx],vect2[mx];
vector<pair<int, int> >  sf;
vector<pair<int,pair<int,int> > > vect;
bool viz[mx];
int n,m,tot,nody;
void citire()
{
    int x,y,i,c;
    fin>>n>>m;
        for(i=1;i<=m;i++)
        {
            fin>>x>>y>>c;
            v[x].push_back(y);
            v[y].push_back(x);
            vect.push_back(make_pair(c,make_pair(x,y)));
        }
fin.close();
}
void dfs(int nod)
{
    viz[nod]=true;
    for(unsigned int i=0;i<vect1[nod].size();++i)
        if(viz[vect1[nod][i]]==false)
        dfs(vect1[nod][i]);
}
void sl()
{
    int i,j,x,y;

    sort(vect.begin(),vect.end());
    int nr=n;
    for(i=0;i<m;++i)
    {
        int cost=vect[i].first;
        int nodx=vect[i].second.first;
         nody=vect[i].second.second;
       //memset(viz,0,sizeof(viz));
       for(int k= 0 ; k < m ; ++ k)
        viz[i]=false;
        dfs(nodx);
        if(viz[nody]==false)
        {
            nr--;
            tot+=cost;
            vect1[nodx].push_back(nody);
            vect2[nody].push_back(nodx);
            sf.push_back(make_pair(nody,nodx));
        }
        if(nr==1) {break;}
    }
    fout<<tot<<'\n';
    fout<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<sf[i].first<<" "<<sf[i].second<<'\n';
}

int main()
{
    citire();
    sl();
        return 0;
}