#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n,m;
struct edge{
    int x,y,c;
};
vector<edge> E,SOL;
int ROOT[100005];
void read(){
    int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        E.push_back({x,y,c});
    }
}
bool cmp(edge e1, edge e2){
    return e1.c<e2.c;
}
int getRoot(int x){
    if(ROOT[x]==x)
        return x;
    ROOT[x]=getRoot(ROOT[x]);
    return ROOT[x];
}
void uni(int x, int y){
    x=getRoot(x);
    y=getRoot(y);
    if(x!=y)ROOT[x]=y;
}
void solve(){
    int r=0;
    sort(E.begin(),E.end(),cmp);
    for(int i=1;i<=n;i++)
        ROOT[i]=i;
    for(auto e : E){
        if(getRoot(e.x)!=getRoot(e.y)){
            uni(e.x,e.y);
            r+=e.c;
            SOL.push_back(e);
        }
    }
    out<<r<<"\n"<<SOL.size()<<"\n";
    for(auto x : SOL)
        out<<x.x<<" "<<x.y<<"\n";
}
int main(){
    read();
    solve();
    return 0;
}