#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int NMAX=2*(10e5)+5;
int N,M,node_m;
int parent[NMAX];
int cnt[NMAX];
struct muchie{
    int x,y,cost;
    muchie(){
        x=0; y=0; cost=0;
    }
}m[NMAX];
vector<muchie>sol;
bool comparare(muchie a, muchie b){
    return a.cost<b.cost;
}
int root(int x){
    node_m=x;
    if(parent[x]==x)
        return x;
    return root(parent[x]);
    parent[x]=node_m;
}
void comasare(int a, int b){
    int ra,rb;
    ra=root(a);
    rb=root(b);
    if(ra==rb)
        return;
    if(cnt[ra]<cnt[rb])
        swap(ra,rb);
    cnt[ra]+=cnt[rb];
    parent[rb]=ra;
    return ;
}
int main()
{
    int ans=0;
    in>>N>>M;
    int i,x,y;
    for(i=1; i<=N; i++){
        parent[i]=i;
        cnt[i]=1;
    }
    for(i=1; i<=M; i++)
        in>>m[i].x>>m[i].y>>m[i].cost;
    sort(m+1,m+M+1,comparare);
    for(i=1; i<=M; i=i+1){
        x=m[i].x;
        y=m[i].y;
        if(root(x)!=root(y)){
            ans+=m[i].cost;
            sol.push_back(m[i]);
            comasare(x,y);
        }
    }
    out<<ans<<'\n';
    out<<sol.size()<<'\n';
    for(auto it:sol)
        out<<it.x<<" "<<it.y<<'\n';
    return 0;
}