#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Muchie
{
    int e1,e2,cost;
};
vector <Muchie> G;
vector <Muchie>::iterator it;
vector <int> A,C;
bool crescator(const Muchie &l, const Muchie &r)
{
    return l.cost<r.cost;
}
int main()
{
   long long int n,m,i,nrm=0,mini,maxi,j,costapm=0;
    Muchie k;
    fin>>n>>m;
    C.push_back(0);
    A.push_back(0);
    for(i=1;i<=m;i++)
    {
        fin>>k.e1>>k.e2>>k.cost;
        G.push_back(k);
    }
    sort(G.begin(),G.end(),crescator);
    for(i=1;i<=n;i++)
        C.push_back(i);

    for(i=1;nrm<n-1;i++)
        if(C.at(G.at(i-1).e1)!=C.at(G.at(i-1).e2))
        {
            nrm++;
            A.push_back(i);
            costapm+=G.at(i-1).cost;
            if(C.at(G.at(i-1).e1)>C.at(G.at(i-1).e2))
            {
                maxi=C.at(G.at(i-1).e1);
                mini=C.at(G.at(i-1).e2);
            }
            else
            {
                maxi=C.at(G.at(i-1).e2);
                mini=C.at(G.at(i-1).e1);
            }
           for(j=1;j<=n;j++)
                if(C.at(j)==maxi)
                    C.at(j)=mini;
        }
    fout<<costapm<<"\n"<<n-1<<"\n";
    for(i=1;i<n;i++)
        fout<<G.at(A.at(i)-1).e2<<" "<<G.at(A.at(i)-1).e1<<"\n";

}