#include <bits/stdc++.h>

using namespace std;

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

int N,M,CostTotal;
int tata[105],rang[105];
vector<pair<int,int>> rez;
vector<pair<int,pair<int,int>>> arrMuchii;

void MakeSet(int x) {
    if(!tata[x]) {
        rang[x]=0;
        tata[x]=x;
    }
}

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

bool Union(int x,int y) {
    x=Find(x);
    y=Find(y);
    if(x==y) return 0;
    
    if(rang[x]>rang[y]) {
        tata[y]=x;
    }
    else if(rang[x]<rang[y]) {
        tata[x]=y;
    }
    else {
        ++rang[x];
        tata[y]=x;
    }
    
    return 1;
}

void Kruskal() {
    for(int i=0;i<arrMuchii.size();++i) {
        int x=arrMuchii[i].second.first;
        int y=arrMuchii[i].second.second;
        if(Union(x,y)) {
            CostTotal+=arrMuchii[i].first;
            rez.push_back({x,y});
        }
    }
}

int main()
{
    fin>>N>>M;
    for(int i=0;i<M;++i) {
        int x,y,cost;
        fin>>x>>y>>cost;
        MakeSet(x);
        MakeSet(y);
        arrMuchii.push_back({cost,{x,y}});
    }
    
    sort(arrMuchii.begin(),arrMuchii.end(),[](pair<int,pair<int,int>> a,pair<int,pair<int,int>> b) { return a.first<b.first; });
    
    Kruskal();
    
    fout<<CostTotal<<endl<<rez.size()<<endl;
    for(const auto& a:rez) {
        fout<<a.first<<' '<<a.second<<endl;
    }

    return 0;
}