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


int dsf_find(int x, vector<int> &parent)
{
    int p=x;
    while(parent[p]!=p) p=parent[p];
    int t=x;
    while(x!=p){
        t=parent[x];
        parent[x]=p;
        x=t;
    };
    return p;
}


void dsf_union(int x, int y, vector<int> &parent, vector<int> &rank)
{
    int px = dsf_find(x,parent);
    int py = dsf_find(y,parent);

    if(px!=py){
        if(rank[px]>rank[py]) parent[py]=px;
        else if(rank[px]<rank[py]) parent[px]=py;
        else {
            parent[px]=py;
            rank[py]++;
        }
    }
}



int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    int n,m;
    fin>>n>>m;

    vector<pair<int,pair<int,int>>> e(m);
    for(auto &p:e)
        fin>>p.second.first>>p.second.second>>p.first;

    sort(e.begin(),e.end());
    
    vector<int> parent(n+1), rank(n+1,0);
    for(int i=1;i<=n;++i)
        parent[i]=i;

    int cst=0;
    int nr=0;

    for(auto &pp : e){
        auto &p = pp.second;
        int pf = dsf_find(p.first,parent);
        int ps = dsf_find(p.second,parent);

        if(pf!=ps){
            cst+=pp.first;            
            ++nr;
            dsf_union(pf,ps,parent,rank);
        }
        else p.first=p.second=-1;
    }

    fout<<cst<<'\n';
    fout<<nr<<'\n';
    for(auto &pp :e){
        auto &p=pp.second;
        if(p.first!=-1){
            fout<<p.first<<' '<<p.second<<'\n';
        }
    }
}