#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n,m,total;
struct triple{
    int first;
    int second;
    int cost;
};
bool comparator(const triple &a ,const triple &b)
{
    return a.cost<b.cost;
}
vector<triple> M;
vector<int> T,R;
vector<pair<int,int>> ans;
set<int> F;
int find(int nod)
{
    if(T[nod]==nod)
       return nod;
    else
     {
        T[nod]=find(T[nod]);
        return T[nod];
     }
}
int main()
{
    cin>>n>>m;
    M.resize(m);
    T.resize(n+1);
    R.resize(n+1);
    for(int i=1;i<=n;i++)
       T[i]=i;
    for(int i=0;i<m;i++)
     cin>>M[i].first>>M[i].second>>M[i].cost;
    sort(M.begin(),M.end(),comparator);
    for(int i=0;i<m;i++)
    {
       int rk=find(M[i].first);
       int rp=find(M[i].second);
       if(rp!=rk)
       {
           if(R[rp]>R[rk])
              T[rk]=rp;
            else
             {
                T[rp]=rk;
                if(R[rk]==R[rp])
                   R[rk]++;
             }
         total=total+M[i].cost;
         F.insert(M[i].first);
         F.insert(M[i].second);
         ans.push_back({M[i].first,M[i].second});
         if(F.size()==n)
            break;
       }
    }
    cout<<total<<'\n';
    cout<<ans.size()<<'\n';
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].first<<" "<<ans[i].second<<'\n';
    return 0;
}