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

using namespace std;



int s(pair < pair<int, int> , int > x, pair < pair<int, int> , int > y)
{
    if(x.second > y.second)
        return 0;
    return 1;
}

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];



int main()
{
    in >> n >> m;
    for(i=1; i<=m; i++)
    {
        in >> l[i].first.first >> l[i].first.second >> l[i].second;
    }

    sort(l+1, l+m+1, s);

    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;
            }
        }
    }

    g  << ct<<"\n"<<n-1<<"\n";

    for(i=1; i<=m; i++)
    {
        if(f[i])
        {
            g<< l[i].first.first << " " << l[i].first.second << "\n";
        }
    }

    return 0;

}