#include <fstream>
#include<vector>
#include<cstdlib>
#include<utility>
#include<queue>
#include<deque>
using namespace std;
struct muchii
{
    int a,b,c;
};
vector <muchii> l;
void quickSort(int left, int right) {

      int i = left, j = right;
      muchii tmp;
      muchii pivot = l[(left + right) / 2];
      while (i <= j)
    {
            while (l[i].c < pivot.c)
                  i++;
            while (l[j].c > pivot.c)
                  j--;
            if (i <= j)
            {
                  tmp = l[i];
                  l[i] = l[j];
                  l[j] = tmp;
                  i++;
                  j--;
            }
      };
      if (left < j)
            quickSort(left, j);

      if (i < right)
            quickSort(i, right);

}
vector <pair <int,int> > lista[200001];
int main()
{
    int n,m;
    ifstream f("apm.in");
    ofstream g("apm.out");
    vector <bool> viz;
    int x,y,C;
    f>>n>>m;
    //lista.resize(n);
    for(int i=0;i<m;i++)
    {
        f>>x>>y>>C;
        muchii M;
        M.a=x;
        M.b=y;
        M.c=C;
        l.push_back(M);
    }
    quickSort(0,m-1);
    queue <pair <int ,int> > arb;
    for(int i=0;i<m;i++)
    {
       lista[l[i].a].push_back(make_pair(l[i].b, l[i].c));
       lista[l[i].b].push_back(make_pair(l[i].a, l[i].c));
    }
    viz.resize(n,false);
    long cost=0;
    int poz=l[0].a;
    for(int i=0;i<n;i++)
    {
        int poz2;
        bool ales=false;
        for(size_t j=0;j<lista[poz].size();j++)
        {
            if(viz[lista[poz][j].first]==false)
            {
                cost+=lista[poz][j].second;
                arb.push(make_pair(poz,lista[poz][j].first));
                poz2=lista[poz][j].first;
                viz[poz]=true;
                viz[lista[poz][j].first]=true;
                ales=true;
                break;
            }
        }
        if(ales==false)
        {
            for(int j=0;j<m&&ales==false;j++)
            {
                if(viz[l[j].a]==true&&viz[l[j].b]==false)
                {
                    poz=l[j].a;
                    poz2=l[j].b;
                    cost+=l[j].c;
                    arb.push(make_pair(poz,poz2));
                    viz[poz2]=true;
                    ales=true;
                }
                else
                    if(viz[l[j].b]==true&&viz[l[j].a]==false)
                {
                    poz=l[j].b;
                    poz2=l[j].a;
                    cost+=l[i].c;
                    arb.push(make_pair(poz,poz2));
                    viz[poz2]=true;
                    ales=true;
                }
            }
        }
        int cost1=1001, cost2=1001, aux1, aux2;
        for(size_t j=0;j<lista[poz].size();j++)
        {
            if(viz[lista[poz][j].first]==false)
            {
                cost1=lista[poz][j].second;
                aux1=lista[poz][j].first;
                break;
            }
        }
        for(size_t j=0;j<lista[poz2].size();j++)
        {
            if(viz[lista[poz2][j].first]==false)
            {
                cost2=lista[poz2][j].second;
                aux2=lista[poz2][j].first;
                break;
            }
        }
        if(cost1<cost2)
        {
            viz[aux1]=true;
            cost+=cost1;
            arb.push(make_pair(poz, aux1));
            poz=aux1;
            i++;
        }
        else
            if(cost1>=cost2&&cost1!=1001)
            {
            viz[aux2]=true;
            cost+=cost2;
            arb.push(make_pair(poz2, aux2));
            poz=aux2;
            i++;
            }
    }
    g<<cost<<"\n"<<n-1<<"\n";
    while(!arb.empty())
    {
        g<<arb.front().first<< " "<<arb.front().second<<"\n";
        arb.pop();
    }
    f.close();
    g.close();
    return 0;
}