#include <fstream>

#include <vector>
#include <queue>

#define N 200000
#define M 400000
#define INF 2000

using namespace std;

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

int CT;
int n, m;
bool viz[N + 1];
vector < pair < int, int > > v[N + 1], rasp;
pair <int, int> mnEdge[N + 1];

void prim_dens(){
    for(int i = 1; i <= n; i++)
        mnEdge[i].first = INF;

    mnEdge[1].first = 0;

    for(int i = 1; i <= n; i++){
        int mnVrt = 0;
        for(int j = 1; j <= n; j++)
            if(!viz[j] && (mnVrt == 0 || mnEdge[j].first < mnEdge[mnVrt].first))
                mnVrt = j;

        viz[mnVrt] = true;
        CT += mnEdge[mnVrt].first;
        if(mnEdge[mnVrt].second != 0)
            rasp.push_back({mnEdge[mnVrt].second, mnVrt});

        for(int j = 0; j < v[mnVrt].size(); j++){
            int nv = v[mnVrt][j].first;
            int cst = v[mnVrt][j].second;
            if(!viz[nv] && cst < mnEdge[nv].first){
                mnEdge[nv].first = cst;
                mnEdge[nv].second = mnVrt;
            }
        }

    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }

    prim_dens();

    fout << CT << '\n';
    fout << n - 1 << '\n';
    for(int i = 0; i < n - 1; i++)
        fout << rasp[i].first << ' ' << rasp[i].second << '\n';

    return 0;
}