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

typedef pair<int,int> PII;
typedef pair<int,PII> PIPII;

int ffind(vector<int> &parent, int a){
    int pa=parent[a];
    while(pa!=parent[pa]) pa=parent[pa];

    int t;
    while(a!=pa){
        t=parent[a];
        parent[a]=pa;
        a=t;
    }

    return pa;
}

void funion(vector<int> &parent,vector<int> &rnk, int a, int b){
    int pa = ffind(parent,a);
    int pb = ffind(parent,b);

    if(rnk[pa]>rnk[pb]){
        parent[pb]=pa;
    }
    else if(rnk[pa]<rnk[pb]){
        parent[pa]=pb;
    }
    else{
       parent[pb]=pa;
       rnk[pa]++;
    }
}


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

    int n,m; fin>>n>>m;

    vector<PIPII> ed(m);
    vector<int> selected(m,0);

    for(int i=0;i<m;++i){
        fin>>ed[i].second.first>>ed[i].second.second>>ed[i].first;
    }

    sort(ed.begin(),ed.end());

    vector<int> parent(n+1);
    for(int i=1;i<=n;++i) parent[i]=i;
    vector<int> rnk(n+1,1);

    int smin=0;

    for(int i=0;i<m;++i){
        int c=ed[i].first;
        int a=ed[i].second.first;
        int b=ed[i].second.second;

        int pa = ffind(parent,a);
        int pb = ffind(parent,b);

        if(pa!=pb){
            smin+=c;
            selected[i]=1;
            funion(parent,rnk,pa,pb);
        }

    }

    fout<<smin<<'\n'<<n-1<<'\n';
    for(int i=0;i<m;++i){
        if(selected[i]){
            fout<<ed[i].second.first<<' '<<ed[i].second.second<<'\n';
        }
    }
}