#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAX_NODES=1005;
struct edge {
    int val,u,v;
};
vector<edge>edges;
vector<pair<int,int>>sol;
bool cmp(edge a,edge b) {
    return a.val<b.val;
}
int p[MAX_NODES];
int _find(int x) {
    if(p[x]==x) {
        return x;
    }
    p[x]=_find(p[x]);
    return p[x];
}
int main() {
    int n,m;
    fin>>n>>m;
    int c;
    for(int i=1; i<=m; i++) {
        edge e;
        fin>>e.u>>e.v>>e.val;
        edges.emplace_back(e);
    }
    for(int i=1; i<=n; i++) {
        p[i]=i;
    }
    sort(edges.begin(),edges.end(),cmp);
    int nr=0;
    long long sum=0;
    for(int i=0; i<edges.size()&&nr<n; i++) {
        int sef1=_find(edges[i].u);
        int sef2=_find(edges[i].v);
        if(sef1!=sef2) {
            nr++;
            p[sef2]=sef1;
            sum+=edges[i].val;
            sol.push_back(make_pair(edges[i].u,edges[i].v));
        }
    }
    fout<<sum<<'\n'<<n-1<<'\n';
    for(auto x:sol) {
        fout<<x.first<<' '<<x.second<<'\n';
    }
    return 0;
}