#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< pair<int, pair<int,int> > > a;
vector< pair<int,int> > sol;
int p[200010],r[200010],n,m;
int gaseste(int x)
{
    if(p[x]!=x) p[x]=gaseste(p[x]);
    return p[x];
}
void unire(int x, int y)
{
    if(r[x]>r[y]) p[y]=x;
    else if(r[y] > r[x]) p[x] = y;
    else{
        p[x] = y;
        r[y] += 1;
    }
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        f>>x>>y>>z;
        a.push_back(make_pair(z,make_pair(x,y)));
    }
    sort(a.begin(),a.end());
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        r[i]=0;
    }
int    tc=0;
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        x=a[i].second.first;
        y=a[i].second.second;
        c=a[i].first;
        int radx=gaseste(x),rady=gaseste(y);
        if(radx!=rady)
        {
            tc+=c;
            unire(radx,rady);
            sol.push_back(make_pair(x,y));
        }
    }
    g<<tc<<"\n"<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
        g<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}