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

int n, m;
int i, j, c, a, b, ct,k=0;
pair < pair<int, int> , int > l[400005];
int v[200005],F[400005];
pair<int,int> sol[200005];
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()
{
    ifstream f ("apm.in");
    f>> n >> m;
    for(i=1; i<=m; i++)
    {
        f >> l[i].first.first >> l[i].first.second >> l[i].second;
    }
    f.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[k].first=a;sol[k++].second=b;
            }

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

       g<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
    g.close();
    return 0;
}