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

struct xxx {int a,b,c;};
vector <xxx> l,sol;
int s(xxx x,xxx y)
{
    if(x.c > y.c)
        return 0;
    return 1;
}

ifstream in ("apm.in");
ofstream g("apm.out");
int n, m;
int i, j, ct;
int v[200005], f[400005];
int main()
{
    in >> n >> m;
    int a,b,c;
    xxx q;
    q.a=q.b=q.c=-INT_MAX+1;
    l.push_back(q);
    for(i=1; i<=m; i++)
    {
        in>>q.a>>q.b>>q.c;
        l.push_back(q);
    }
    make_heap(l.begin()+1,l.end(),s);
    sort_heap(l.begin()+1,l.end(),s);
    v[1]=1;
    for(i=1; i<=m; i++)
    {
        a=l[i].a;
        b=l[i].b;
        c=l[i].c;
        if(!f[i])
        {
            if(v[a] + v[b] ==1)
            {
                ct+=c;
                f[i]++;
                v[a]=v[b]=1;
                i=0;
                q.a=a;
                q.b=b;
                sol.push_back(q);
            }
        }
    }
    g  << ct<<"\n"<<n-1<<"\n";
    for(i=0; i<n-1; i++)
            g<< sol[i].a << " " << sol[i].b << "\n";

    return 0;

}