#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int ma[1001][1001],n,m,arb[1001],c,k;
struct muchie
{
    int x,y,cost;
} v[10001],a[10001];
bool comparare(muchie e,muchie ee)
{
    if(e.cost < ee.cost)
        return 1;
    else
        return 0;
}
void Kruskal()
{
    int ai,aj;
    for(int i=1; i<=n; i++)
        arb[i]=i;
    for(int i=1; i<=m && k<=n-2; i++)
    {
        ai=arb[v[i].x];
        aj=arb[v[i].y];
        if(ai!=aj)
        {
            c=c+v[i].cost;
            a[++k]=v[i];
            for(int j=1; j<=n; j++)
                if(arb[j]==ai)
                    arb[j]=aj;
        }
    }
}
int main()
{
    int x,y,z;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>v[i].x>>v[i].y>>v[i].cost;
    sort(v+1,v+m+1,comparare);
    Kruskal();
    fout<<c<<endl;
    fout<<k<<'\n';
    for(int i=1;i<=k;i++)
        fout<<a[i].x<<" "<<a[i].y<<endl;
    return 0;
}