#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream in ("apm.in");
ofstream g("apm.out");
int n, m;
int i, j, c, a, b, ct;
pair < pair<int, int> , int > l[400005];
int v[200005],f[400005];
vector < pair<int,int> > sol;
bool comp(pair < pair<int, int> , int > x, pair < pair<int, int> , int > y)
{
    if(x.second > y.second)
        return 0;
    return 1;
}
int main()
{
    in >> n >> m;
    for(i=1; i<=m; i++)
    {
        in >> l[i].first.first >> l[i].first.second >> l[i].second;
    }
    in.close();
    sort(l+1, l+m+1, comp);
    v[1]=1;
    for(i=1; i<=m; i++)
    {
        a=l[i].first.first;
        b=l[i].first.second;
        c=l[i].second;
        if(!f[i])
        {
            if(v[a] + v[b] ==1)
            {
                ct+=c;
                f[i]++;
                v[a]=v[b]=1;
                i=0;
                sol.push_back(make_pair(a,b));
            }

        }
    }
    g <<ct<<"\n"<<n-1<<"\n";
    for(i=0; i<n-1; i++)
    {

       g<<sol.at(i).first<<" "<<sol.at(i).second<<"\n";
    }
    g.close();

}