#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int t[200001],rang[200001],n;
int c[400001],x[400001],y[400001],ind[400001],m;
int sol,ksol;
vector < int > v;
bool comp (int i, int j){return c[i] < c[j];}

int multime(int x)
{
    if(t[x]!=x)t[x]=multime(t[x]);
    return t[x];
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)fin>>x[i]>>y[i]>>c[i],ind[i]=i;
    for(int i=1;i<=n;++i)t[i]=i;
    sort(ind+1,ind+m+1,comp);
    for(int i=1;i<=m;++i)
    {
        if(multime(x[ind[i]])!=multime(y[ind[i]]))
        {
            sol+=c[ind[i]];
            if(rang[x[ind[i]]]==rang[y[ind[i]]])rang[x[ind[i]]]++;
            if(rang[x[ind[i]]]<rang[y[ind[i]]])
                 t[multime(x[ind[i]])]=multime(y[ind[i]]);
            else t[multime(y[ind[i]])]=multime(x[ind[i]]);
            v.push_back(ind[i]);
            //for(int j=1;j<=n;j++)
            //   cout<<t[j]<<' ';
            //   cout<<'\n';
        }
    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        fout<<x[v[i]]<<' '<<y[v[i]]<<'\n';


    return 0;
}