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

ifstream f ("apm.in");
ofstream g ("apm.out");
struct Muchie
{
    int x,y;
    double c;
} M[400005];

int n,m,viz[200005];
vector<pair<int, int> > sol;
void cit()
{
    f>>n>>m;
    for(int i=0; i<m; i++)
    {
        f>>M[i].x>>M[i].y>>M[i].c;
    }
}

void sortare()
{
    for(int i = 0; i < m; i++)
        for(int j = i + 1; j < m; j++)
            if(M[i].c > M[j].c)
                swap(M[i], M[j]);
}

void uneste(int a, int b)
{
    for(int i = 1; i <= n; i++)
        if(viz[i] == a)
            viz[i] = b;
}

void apm()
{
    for(int i = 1; i <= n; i++)
        viz[i] = i;

    int cost = 0, cate = 0;
    for(int i = 0; i < m; i++)
        if(viz[M[i].x] != viz[M[i].y])
    {
        cost += M[i].c;
        uneste(viz[M[i].y], viz[M[i].x]);
        sol.push_back(make_pair(M[i].x,M[i].y));
        cate++;
        if(cate == n - 1)
            break;
    }
    g << cost <<"\n";
    g<< n-1 <<"\n";
    for(auto &x:sol)
        g<<x.first<<" "<<x.second<<"\n";
}
int main()
{
    cit();
    sortare();
    apm();
    return 0;
}