#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct muchie
{
    int nx,ny,cost;
    bool operator <(const muchie &other)const
    {
        return cost>other.cost;
    }
};

priority_queue<muchie>pq;
vector<pair<pair<int,int>,int>>Q2;
vector<pair<int,int>>Q;

int n,m,costt;
int apare[200001];


void cit()
{
    f>>n>>m;
    for (int i=1;i<=m;++i)
    {
        int x1,x2,x3;
        f>>x1>>x2>>x3;
        pq.push({x1,x2,x3});
    }
}
void rez()
{
    int siz=0;
    while (!pq.empty())
    {
        bool ok=0;
        int nod=pq.top().nx;
        int vecin=pq.top().ny;
        int cost=pq.top().cost;
        pq.pop();
        if (!apare[nod])
        {
            if (!apare[vecin])
            {
                siz++;
                apare[nod]=apare[vecin]=1;
                Q.push_back({nod,vecin});
                costt+=cost;
                ok=1;
            }
            else
            {
                siz++;
                apare[nod]=1;
                Q.push_back({nod,vecin});
                costt+=cost;
                ok=1;
            }
        }
        else
        {
            if (!apare[vecin])
            {
                siz++;
                apare[vecin]=1;
                Q.push_back({nod,vecin});
                costt+=cost;
                ok=1;
            }
        }
        if (!ok)
            Q2.push_back(make_pair(make_pair(nod,vecin),cost));
    }
    for (vector<pair<pair<int,int>,int>>::iterator g=Q2.begin();siz!=n-1&&g!=Q2.end();++g,++siz)
    {
        int y1=g->first.first;
        int y2=g->first.second;
        int y3=g->second;
        Q.push_back({y1,y2});
        costt+=y3;
    }
}

void afis()
{
    g<<costt<<'\n'<<Q.size()<<'\n';
    for (auto w:Q)
    {
        g<<w.first<<' '<<w.second<<'\n';
    }
}


int main()
{
    cit();
    rez();
    afis();
    return 0;
}