#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie{
    int x,y,cost;
} muchii[400001];

int tata[200001],h[200001];
int solX[200001],solY[200001];

bool cmp(Muchie a,Muchie b){
    return a.cost<b.cost;
}

int find(int x){
    if(tata[x]==x)
        return x;
    return tata[x]=find(tata[x]);
}

void unite(int x,int y){
    x=find(x);
    y=find(y);

    if(h[x]<h[y])
        swap(x,y);

    tata[y]=x;

    if(h[x]==h[y])
        h[x]++;
}

int main(){
    int n,m;
    fin>>n>>m;

    for(int i=1;i<=m;i++)
        fin>>muchii[i].x>>muchii[i].y>>muchii[i].cost;

    sort(muchii+1,muchii+m+1,cmp);

    for(int i=1;i<=n;i++)
        tata[i]=i;

    int costTotal=0,nr=0;

    for(int i=1;i<=m&&nr<n-1;i++){
        int x=muchii[i].x;
        int y=muchii[i].y;

        if(find(x)!=find(y)){
            unite(x,y);
            nr++;
            costTotal+=muchii[i].cost;
            solX[nr]=x;
            solY[nr]=y;
        }
    }

    fout<<costTotal<<'\n';
    fout<<nr<<'\n';

    for(int i=1;i<=nr;i++)
        fout<<solX[i]<<' '<<solY[i]<<'\n';

    return 0;
}