#include <fstream>

using namespace std;

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

#define Nmax 2001
#define oo 1001

int cx[Nmax];
int cy[Nmax];

int legatura[Nmax][Nmax];
int cost[Nmax][Nmax];

int minim(int n, int j, int &good_one)
{
    int valMIN = 1001;
    for(int i = 1; i<=n; i++)
    {
        if(legatura[i][j]==1)
        {
            if(cost[i][j] < valMIN)
            {
                valMIN = cost[i][j];
                good_one = i;
            }

        }
    }
    return valMIN;
}

int main()
{
    int n,m,i,j;

    in>>n>>m;

    int x,y,c;
    int k=0;
    for(i = 1; i<=m; i++)
    {
        in>>x>>y>>c;
        legatura[x][y] = legatura[y][x] = 1;
        cost[x][y] = cost[y][x] = c;
    }
    int good_one;
    int valMIN;
    int sumaMinima=0;

    for(int j = n; j>1; j--)
    {
        valMIN = minim(n,j,good_one);
        sumaMinima+=valMIN;
        cost[good_one][j] = cost[j][good_one] = 1002;
        cx[k] = good_one;
        cy[k] = j;
        k++;
    }
    out<<sumaMinima;
    out<<'\n'<<n-1<<'\n';
    for(int i =0; i<k; i++)
        out<<cx[i]<<" "<<cy[i]<<'\n';
    return 0;
}