#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define minim(a, b) ((a<b)?a:b)
#define maxim(a, b) ((a>b)?a:b)
#define nmax 200001
struct muchie
{
    int x, y, c;
    /*bool operator<(const muchie &a) const
    {
        return c<a.c;
    }*/
};
vector <muchie> v;
int n, m, cost=0, sol[nmax];
bool cmp(muchie a, muchie b)
{
    return a.c<b.c;
}
void citire()
{
    fin>>n>>m;
    muchie a;
    int k;
    for(k=1; k<=m; k++)
    {
        fin>>a.x>>a.y>>a.c;
        v.push_back(a);
    }
    fin.close();
}
void kruskal()
{
    int c[nmax], i, k, j, mn, mx;
    for(i=1; i<=n; i++)
        c[i]=i;
    k=0; i=0;
    while(k<n-1 && i<m)
    {
        if(c[v[i].x]!=c[v[i].y])
        {
            k++;
            sol[k]=i;
            cost+=v[i].c;
            mn=minim(c[v[i].x], c[v[i].y]);
            mx=maxim(c[v[i].x], c[v[i].y]);
            for(j=1; j<=n; j++)
                if(c[j]==mx)
                    c[j]=mn;
        }
        i++;
    }
}
void afisare()
{
    int i;
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=1; i<=n-1; i++)
        fout<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';
    fout.close();
}
int main()
{
    citire();
    sort(v.begin(), v.end(), cmp);
    kruskal();
    afisare();
    return 0;
}