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