#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
#include <vector>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");
struct Muchie
{
    int nod1,nod2,cost;
};
bool cmp(Muchie A, Muchie B)
{
    if(A.cost<B.cost)
        return true;
    return false;
}
int main()
{
    int n,m,x;
    in>>n>>m;
    vector<vector<int>> G(n+1);
    vector<Muchie>sol;
    vector<Muchie>A(m+1);
    long long cost=0;
    vector<int> comp(n+1);
    for(int i=1;i<=n;i++)
    {
        G[i].push_back(i);
        comp[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        in>>A[i].nod1>>A[i].nod2>>A[i].cost;
    }
    sort(A.begin(),A.end(),cmp);
    for(auto i: A)
    {
        if(comp[i.nod1]!=comp[i.nod2])
        {
            cost=cost+i.cost;
            sol.push_back(i);
            if(G[comp[i.nod1]].size()<G[comp[i.nod2]].size())
            {
                for(auto j: G[comp[i.nod1]])
                {
                    G[comp[i.nod2]].push_back(j);
                    comp[j]=comp[i.nod2];
                }
            }
            else
                for(auto j: G[comp[i.nod2]])
                {
                     G[comp[i.nod1]].push_back(j);
                     comp[j]=comp[i.nod1];
                }
        }
   }
    out<<cost<<"\n";
    out<<n-1<<"\n";
    for(auto i: sol)
    {
        out<<i.nod1<<" "<<i.nod2<<"\n";
    }
    return 0;


}