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

using namespace std;

vector<pair<int, int> > a[NMAX];
multiset<pair<int, int> > s;
int n, m, apm=0, D[NMAX], vz[NMAX], prec[NMAX];

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

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

    f>>n>>m;
    while (m--)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(c, y));
        a[y].push_back(make_pair(c, x));
    }
}

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

    s.insert(make_pair(0, 1));

    for (i=2; i<=n; ++i) D[i]=INF;

    while (nr<n && !s.empty())
    {
        pr=*s.begin(); s.erase(s.begin());

        if (!vz[pr.s])
        {
            vz[pr.s]=1;apm+=D[pr.s]; ++nr;

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

                if (!vz[r.s] && D[r.s]>r.f)
                {
                    D[r.s]=r.f; prec[r.s]=pr.s;
                    s.insert(make_pair(r.f, r.s));
                }
            }
        }
    }
}

void Scrie()
{
    int i;

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

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

int main()
{
    Citeste();

    Solve();

    Scrie();

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