#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=200000;
class Forest{
    public:
        int father[N+1];
        Forest(){
        }
        Forest(int n){
            int i;
            for(i=1;i<=n;i++)
                father[i]=i;
        }
        int set(int x){
            if(father[x]==x)
                return x;
            father[x]=set(father[x]);
            return father[x];
        }
};
class Edge{
    public:
        int v1,v2,cost;
        Edge(){
        }
        Edge(int vert1,int vert2,int c){
            this->v1=vert1;
            this->v2=vert2;
            this->cost=c;
        }
        bool operator<(const Edge&e)const{
            return this->cost<e.cost;
        }
};
Edge e[N+1],e_tree[N+1];
Forest f;
FILE*in,*out;
int n,m,tCost;
void scan(){
    int i,v1,v2,c;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(in,"%d%d%d",&v1,&v2,&c);
        e[i]=Edge(v1,v2,c);
    }
}
void init(){
    in=fopen("apm.in","r");
    out=fopen("apm.out","w");
    scan();
    f=Forest(n);
}
int min2(int a,int b){
    if(a<b)
        return a;
    return b;
}
int max2(int a,int b){
    if(a>b)
        return a;
    return b;
}
void mst(){
    int i,noE_tree=0;
    sort(e+1,e+m+1);
    for(i=1;i<=m;i++)
        if(f.set(e[i].v1)!=f.set(e[i].v2)){
            f.father[f.set(e[i].v1)]=f.set(e[i].v2);
            tCost+=e[i].cost;
            e_tree[++noE_tree]=e[i];
        }
}
void print(){
    int i;
    fprintf(out,"%d\n%d\n",tCost,n-1);
    for(i=1;i<n;i++)
        fprintf(out,"%d %d\n",e_tree[i].v1,e_tree[i].v2);
}
void solve(){
    mst();
    print();
}
int main(){
    init();
    solve();
    return 0;
}