#include <bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream o("apm.out");

int n,m;
int matei;
int sef[200001];
vector <int> arbore[200001];

struct elem{
    int x;
    int y;
    int cost;
};
bool ord(elem A, elem B){
    return A.cost<B.cost;
}
elem muchii[400001];

int boss(int nod){
    if(sef[nod]==nod)
        return nod;
    else{
        sef[nod]=boss(sef[nod]);
        return sef[nod];
    }
}

void unire(int a, int b){
    int sefu_lua=boss(a);
    int sefu_lub=boss(b);
    sef[sefu_lub]=sefu_lua;
}

int main()
{
    f>>n>>m;
    int nr_muchii_pttest=0;
    for(int i=1;i<=m;i++){
        f>>muchii[i].x>>muchii[i].y>>muchii[i].cost;
    }
    sort(muchii+1, muchii+m+1, ord);
    for(int i=1;i<=n;i++)
        sef[i]=i;
    for(int i=1;i<=m;i++){
        int a=muchii[i].x;
        int b=muchii[i].y;
        if(boss(a)!=boss(b)){
            matei+=muchii[i].cost;
            unire(a,b);
            nr_muchii_pttest++;///n-1
            arbore[a].push_back(b);
        }
    }
    o<<matei<<'\n'<<nr_muchii_pttest<<'\n';
    for(int i=1;i<=n;i++)
        for(int j=0;j<arbore[i].size();j++)
            o<<i<<' '<<arbore[i][j]<<'\n';
    return 0;
}