#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector < pair<int , pair<int,int> > > v;
vector <int> sol;
int a, b, c,x,y, n,t,s, m,p[200010];


int findx(int x){
    if(p[x]<0)
        return x;
    else
        return x=findx(p[x]);

}
void unionx(int a,int b )
{
    int parenta=findx(a);
    int parentb=findx(b);
    if(p[parenta]>p[parentb])
        p[parenta]=parentb;
    else if(p[parenta]<p[parentb])
        p[parentb]=parenta;
    else{
        p[parenta]=parentb;
        p[parentb]--;

    }
}


int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
{
    fin>>a>>b>>c;
    v.push_back(make_pair(c,make_pair(a,b)));

}
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    p[i]=-1;

    for(int i=0;i<m;i++)
    {
        x=findx(v[i].second.first);
        y=findx(v[i].second.second);
        if(x!=y){
            s+=v[i].first;
            unionx(v[i].second.first,v[i].second.second);
            sol.push_back(v[i].second.second);
            t++;
            sol.push_back(v[i].second.first);
            t++;


        }
        if(t/2==n-1)
            break;



    }
    fout<<s<<'\n'<<t/2<<'\n';
    for(int i=0;i<sol.size()-1;i++)
    {
        fout<<sol[i]<<" "<<sol[i+1]<<'\n';
        i++;
    }

    return 0;
}