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

using namespace std;
#define MaxM 400000
struct st
{
    int x;
    int y;
    int cost;
};

st a[MaxM];
int t[MaxM], rasp[MaxM];
int tata(int k)
{
    if(t[k]==k)
        return k;
    int aux;
    aux=tata(t[k]);
    t[k]=aux;
    return aux;
}

bool cmp(const st& i, const st& j)
{
    return i.cost<j.cost;
}
int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    int n, m, i, j, sum=0, cnt=0;
    in>>n>>m;
    for(i=0; i<m; i++)
    {
        in>>a[i].x>>a[i].y>>a[i].cost;
    }

    sort(a, a+m, cmp);
    for(i=1; i<=n; i++) t[i]=i;
    for(i=0; i<m; i++)
    {
        if(tata(a[i].x)!=tata(a[i].y))
        {
            t[tata(a[i].x)]=a[i].y;
            sum=sum+a[i].cost;
            rasp[cnt]=i;
            cnt++;
        }
    }
    out<<sum<<'\n'<<cnt<<'\n';
    for(i=0; i<cnt; i++)
    {
        out<<a[i].x<<" "<<a[i].y<<'\n';
    }
    return 0;
}