#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,m,n,T[200010],A[200010],x,y,a,c,cost;
vector<pair<int,pair<int,int>>> E;
vector<pair<int,int>> sol;
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)T[i]=i;
    for(;m;m--)
    {
        f>>x>>y>>c;
        E.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(E.begin(),E.end());
    for(auto it:E)
    {
        c=it.first;
        for(x=it.second.first;T[x]-x;x=T[x])A[++a]=x;for(;a;)T[A[a--]]=x;y=x;
        for(x=it.second.second;T[x]-x;x=T[x])A[++a]=x;for(;a;)T[A[a--]]=x;
        if(x!=y)
        {
            T[x]=y;
            cost+=c;
            sol.push_back(it.second);
        }
    }
    g<<cost<<'\n';
    g<<n-1<<"\n";
    for(auto it:sol)
        g<<it.first<<" "<<it.second<<'\n';

    return 0;
}