#include<fstream>
#include<list>
#include<algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MMAX=400005,NMAX=200005;
struct graph{
    int from,to,cost;
};
graph edges[MMAX];
list<pair<int,int>>apm;
int n,m,cost_apm;
int tree[NMAX],height[NMAX];
bool cmp(const graph &a,const graph &b){
    return a.cost<b.cost;
}
void read_data(){
    int i,from,to,cost;
    fin>>n>>m;
    for(i=1;i<=m;++i){
        fin>>from>>to>>cost;
        edges[i]={from,to,cost};
        tree[i]=i;
        height[i]=1;
    }
    sort(edges+1,edges+1+m,cmp);
}
int same_tree(int x){
    int root,aux;
    for(root=x;root!=tree[root];root=tree[root]);
    while(tree[x]!=x){
        aux=tree[x];
        tree[x]=root;
        x=aux;
    }
    return root;
}
void unite(int x,int y){
    if(height[x]>height[y])
        tree[y]=x;
    else
        tree[x]=y;
    if(height[x]==height[y])
        ++height[y];
}
void kruskal(){
    int i;
    for(int i=1;i<=m;++i){
        int node1=edges[i].from;
        int node2=edges[i].to;
        int cost=edges[i].cost;
        int find_node1=same_tree(node1);
        int find_node2=same_tree(node2);
        if(find_node1!=find_node2){
            cost_apm+=cost;
            apm.push_back(make_pair(node1,node2));
            unite(find_node1,find_node2);
        }
    }
}
void afisare(){
    fout<<cost_apm<<'\n'<<apm.size()<<'\n';
    list<pair<int,int>>::iterator it;
    for(it=apm.begin();it!=apm.end();++it)
        fout<<it->first<<' '<<it->second<<'\n';
}
int main(){
    read_data();
    kruskal();
    afisare();
}