#include<fstream>
#include<list>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=200005;
list<pair<int,int>>g[NMAX];
list<pair<int,pair<int,int>>>edges;
list<pair<int,int>>apm;
int n,m,cost_apm;
int tree[NMAX],height[NMAX];
bool cmp(const pair<int,pair<int,int>>&a,const pair<int,pair<int,int>>&b){
    return a.second.second<b.second.second;
}
void read_data(){
    int i,from,to,cost;
    fin>>n>>m;
    for(i=1;i<=m;++i){
        fin>>from>>to>>cost;
        g[from].push_back(make_pair(to,cost));
        edges.push_back(make_pair(from,make_pair(to,cost)));
        tree[i]=i;
        height[i]=1;
    }
    edges.sort(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;
    }
}
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(){
    list<pair<int,pair<int,int>>>::iterator it;
    for(it=edges.begin();it!=edges.end();++it){
        int node1=it->first;
        int node2=(it->second).first;
        int cost=(it->second).second;
        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();
}