#include<fstream>
#include<queue>
#include<vector>
#include<utility>
#define NMAX 200010
#define f first
#define s second

using namespace std;

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

vector<pair<int, int> > a[NMAX], sol;

priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;

int n, m, apm, vz[NMAX], D[NMAX], prec[NMAX];

void Citeste()
{
    int i, x, y, c;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;

        a[x].push_back(make_pair(c, y));
        a[y].push_back(make_pair(c, x));
    }

    for (i=1; i<=n; ++i) D[i]=NMAX;
}

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

    q.push(make_pair(0, 1)); D[1]=0; prec[1]=-1;

    while (!q.empty())
    {
        pr=q.top(); q.pop();

        if (!vz[pr.s])
        {
            if (prec[pr.s]!=-1)
            {
                sol.push_back(make_pair(prec[pr.s], pr.s));
                apm+=pr.f;
                vz[pr.s]=1;
            }
            else vz[pr.s]=1;

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

                if (D[r.s]>r.f && !vz[r.s])
                {
                    q.push(make_pair(r.f, r.s));
                    D[r.s]=r.f;
                    prec[r.s]=pr.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();

    Solve();

    Scrie();

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