// Algoritmul lui Prim cu heap-uri - 100p - O(n*log(n))

#include <fstream>
#include <vector>
#include <queue>
#define nmax 200005
#define inf 2e9
#define PII pair<int,int>


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

priority_queue<pair<int, PII>, vector<pair<int,PII> >, greater<pair<int,PII> > >h;
vector<PII> v[nmax];
int n,m,viz[nmax];

struct apm
{
    int x,y;
} sol[nmax];

int prim(int nod)
{
    int i, j, vecin, cost, ct=0;

    viz[nod]=1;

    for(i=1; i<n; i++)
    {
        for(j=0; j<v[nod].size(); j++)
        {
            vecin = v[nod][j].second;
            cost = v[nod][j].first;
            if(!viz[vecin]) h.push({cost,{nod,vecin}});
        }

        while(viz[h.top().second.second]) h.pop();

        ct += h.top().first;
        viz[h.top().second.second] = 1;
        sol[i].x = h.top().second.first;
        sol[i].y = h.top().second.second;
        nod = h.top().second.second;
        h.pop();
    }
    return ct;
}

int main()
{
    int a,b,c,i;

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

    }

    g<<prim(1)<<'\n'<<n-1<<'\n';
    for(i=1; i<n; i++)
    {
        g<<sol[i].x<<" "<<sol[i].y<<'\n';
    }
    return 0;
}