#include<fstream>
#include<vector>
#include<set>
#include<utility>
#define NMAX 200010
#define INF 200010000
#define f first
#define s second

using namespace std;

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

struct muchie
{
    int nod, cost;
};

int n, m, d[NMAX], tata[NMAX], vz[NMAX];

multiset< pair<int, int> > s;
multiset< pair<int, int> > :: iterator is;

vector<muchie> a[NMAX];

void Citeste()
{
    int i, x, y;
    muchie r;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>r.cost;
        r.nod=y; a[x].push_back(r);
        r.nod=x; a[y].push_back(r);
    }
}

void Solve()
{
    int i, valapm=0, nr=0, apm=0;
    muchie r;
    pair<int, int > pr;

    for (i=1; i<=n; ++i) d[i]=INF;

    d[1]=0; s.insert(make_pair(0, 1));

    do
    {
        do
        {
            is=s.begin();
            pr=*is;
            if (vz[pr.s]) s.erase(is);
        }while(vz[pr.s]);

        apm+=pr.f; vz[pr.s]=1; s.erase(is); ++nr;

        for (i=0; i<a[pr.s].size(); ++i)
        {
            r=a[pr.s][i];

            if (!vz[r.nod] && d[r.nod]>r.cost)
            {
                d[r.nod]=r.cost; tata[r.nod]=pr.s;
                s.insert(make_pair(r.cost, r.nod));
            }
        }

    }while (nr<n);

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

    for (i=2; i<=n; ++i) g<<tata[i]<<" "<<i<<"\n";
}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();

    return 0;
}