#include<fstream>
#include<vector>
#include<algorithm>
#include<utility>
#define MMAX 400010
#define NMAX 250010
#define f first
#define s second

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

vector < pair <int, pair <int, int> > > v;
vector < pair <int, int> > sol;
int n, m, apm=0, h[NMAX], t[NMAX];

void Citeste()
{
    int i, a, b, c;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>a>>b>>c;
        v.push_back( make_pair(c, make_pair(a, b)) );
    }
}

void Init()
{
    int i;

    for (i=1; i<=n; ++i)
    {
        h[i]=1; t[i]=i;
    }
}

int tata(int nod)
{
    if (t[nod]==nod) return nod;
    return tata(t[nod]);
}

int Uneste(int x, int y)
{
    int tx=tata(x), ty=tata(y);

    if (h[tx]<h[ty]) t[tx]=ty;
    else
        if (h[ty]<h[tx]) t[ty]=tx;
        else
        {
            h[tx]++;
            t[ty]=tx;
        }
}

void Solve()
{
    int i;
    pair<int, pair<int, int> > pr;

    sort(v.begin(), v.end());

    for (i=0; i<v.size(); ++i)
    {
        pr=v[i];

        if (tata(pr.s.f)!=tata(pr.s.s))
        {
            Uneste(pr.s.f, pr.s.s);
            apm+=pr.f; sol.push_back(make_pair(pr.s.f, pr.s.s));
        }
    }
}

void Scrie()
{
    int i;

    g<<apm<<"\n"<<n-1<<"\n";

    for (i=0; i<n-1; ++i) g<<sol[i].f<<" "<<sol[i].s<<"\n";
}

int main()
{
    Citeste();

    Init();

    Solve();

    Scrie();

    f.close();
    g.close();
    return 0;
}