#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

vector < vector <int> > muchii;
vector <pair <int, int> > muchii_finale;
int n, m, cost=0;
int viz[200000];

bool comp (vector <int> a, vector <int> b) {
   return a[2]<b[2];
}

void citire ()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    for (int i=0; i<m; i++)
    {
        vector <int> temp;
        int p1, p2, c;
        fin>>p1>>p2>>c;
        temp.push_back(p1-1);
        temp.push_back(p2-1);
        temp.push_back(c);
        muchii.push_back(temp);
    }
}

void prim_basic ()
{
    viz[muchii[0][0]]=1;
    int k=0, i=0;
    while (k<n-1)
    {
        if (viz[muchii[i][0]]==1 && viz[muchii[i][1]]==0)
        {
            k++;
            viz[muchii[i][1]]=1;
            cost+=muchii[i][2];
            for (int j=0; j<i; j++)
            {
                if (viz[muchii[j][0]]==1 && viz[muchii[j][1]]==0)
                {
                    k++;
                    viz[muchii[j][1]]=1;
                    muchii_finale.push_back(make_pair (muchii[j][0], muchii[j][1]));
                    cost+=muchii[j][2];
                }
                else if (viz[muchii[j][0]]==0 && viz[muchii[j][1]]==1)
                {
                    k++;
                    viz[muchii[j][0]]=1;
                    muchii_finale.push_back(make_pair (muchii[j][0], muchii[j][1]));
                    cost+=muchii[j][2];
                }
            }
            muchii_finale.push_back(make_pair (muchii[i][0], muchii[i][1]));
        }
        else if (viz[muchii[i][0]]==0 && viz[muchii[i][1]]==1)
        {
            k++;
            viz[muchii[i][0]]=1;
            cost+=muchii[i][2];
            for (int j=0; j<i; j++)
            {
                if (viz[muchii[j][0]]==1 && viz[muchii[j][1]]==0)
                {
                    k++;
                    viz[muchii[j][1]]=1;
                    muchii_finale.push_back(make_pair (muchii[j][0], muchii[j][1]));
                    cost+=muchii[j][2];
                }
                else if (viz[muchii[j][0]]==0 && viz[muchii[j][1]]==1)
                {
                    k++;
                    viz[muchii[j][0]]=1;
                    muchii_finale.push_back(make_pair (muchii[j][0], muchii[j][1]));
                    cost+=muchii[j][2];
                }
            }
            muchii_finale.push_back(make_pair (muchii[i][0], muchii[i][1]));
        }
        i++;
    }
}


int main()
{
    citire();
    sort (muchii.begin(), muchii.end(), comp);
    prim_basic();
    ofstream fout("apm.out");
    fout<<cost<<endl;
    fout<<n-1<<endl;
    for (int i=0; i<muchii_finale.size(); i++) {
        fout<<muchii_finale[i].first+1<<" "<<muchii_finale[i].second+1<<endl;
    }
    return 0;
}