#include <bits/stdc++.h>
using namespace std;
ifstream r("apm.in");
ofstream w("apm.out");
const int N=400005;
struct s {
    int x,y,z;
}e[N];
bool c(s a, s b){return a.z<b.z;}
int n,m,k,i,z,t[N];
pair<int,int>a[N];
int f(int nod){if(t[nod]==nod)return nod;return t[nod]=f(t[nod]);}
int main()
{
    r>>n>>m;
    for(i=1;i<=m;i++){r>>e[i].x>>e[i].y>>e[i].z;};
    for(i=1;i<=n;i++)t[i]=i;
    sort(e+1,e+m+1,c);
    for(i=1;i<=m;i++) {int x=f(e[i].x),y=f(e[i].y);if(x==y)continue;z+=e[i].z;t[x]=y;a[++k]={e[i].x,e[i].y};}
    w<<z<<"\n"<<k<<"\n";
    for(i=1;i<=k;i++)w<<a[i].first<<" "<<a[i].second<<"\n";
    return 0;
}