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

ifstream f("apm.in");
ofstream g("apm.out");
struct Muchie
{
    int x,y,cost;
};
bool cmp(Muchie NOD1, Muchie NOD2)
{
    if(NOD1.cost<NOD2.cost) return 1;
    return 0;
}
int main()
{
    int n,m, cost=0;
    f>>n>>m;

    vector <Muchie> Graph, Sol;
    vector <int> comp(n+1);
    vector < vector <int> > L(n+1);

    for (int i=1;i<=n;i++)
    {
        comp[i]=i;
        L[i].push_back(i);
    }

    for (int i=1;i<=m;i++)
    {
        Muchie NOD;
        f>>NOD.x>>NOD.y>>NOD.cost;
        Graph.push_back(NOD);
    }
    sort (Graph.begin(),Graph.end(),cmp);

    for (auto i:Graph)
    {
        int cx=comp[i.x];
        int cy=comp[i.y];
        if (cx!=cy)
        {
            cost+=i.cost;
            Sol.push_back(i);
            if (L[cx].size()<L[cy].size())
            {
                auto p=L[cx].begin(), q=L[cx].end();
                for (auto i=p;i!=q;i++)
                {
                    comp[(*i)]=cy;
                    L[cy].push_back((*i));
                }
            }
            else
            {
                auto p=L[cy].begin(), q=L[cy].end();
                for (auto i=p;i!=q;i++)
                {
                    comp[(*i)]=cx;
                    L[cx].push_back((*i));
                }
            }
        }
    }
    g<<cost<<'\n'<<n-1<<'\n';
    for (auto i:Sol)
    {
        g<<i.x<<' '<<i.y<<'\n';
    }
    return 0;
}