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

const int Nmax = 200005;

using namespace std;
ifstream fin("apl1.in");
ofstream fout("apl1.out");
pair<int,pair<int,int> >muchie[Nmax];
vector<int> Arb[Nmax];
vector<pair<int,int> > ans;
int v[Nmax],M,N; /// v[i] = in ce componenta conexa se afla i

void init(){
    for(int i = 1; i <= N; ++i)
        v[i] = i; /// initial toate nodurile se afla in comp lor proprie
}

void cuplam(int x,int y){
    ///Arb[x].push_back(y); /// formam arborele
    ///Arb[y].push_back(x);
    ans.push_back(make_pair(x,y));
    int val = v[x];
    for(int i = 1; i <= N; i++)
        if(v[i] == val)
            v[i] = v[y];
}

int main()
{
    int a,b,c;
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> a >> b >> c;
        muchie[i] = make_pair(c,make_pair(a,b));
    }
    sort(muchie+1,muchie+M+1);
    /** afisaj sortare
        for(int i = 1; i <= M; i++){
        fout << muchie[i].second.first << " " << muchie[i].second.second << " ";
        fout << muchie[i].first << "\n";
    }*/
    init();
    int cost = 0;
    for(int i = 1; i <= M; ++i)
    {
        int x,y;
        x = muchie[i].second.first;
        y = muchie[i].second.second;
        if(v[x] == v[y])continue; /// sare inapoi la for daca e adevarat if-ul
        cuplam(x,y);
        cost += muchie[i].first;
    }
    fout << cost << "\n" << N - 1 << "\n";
    for(int i = 0; i < ans.size(); ++i)
        fout << ans[i].first << " "<< ans[i].second << "\n";
    /**
    for(int i = 1; i <= N; ++i)
        for(int j = 0; j < Arb[i].size(); j ++)
            if( i < Arb[i][j])
                fout << i << " " << Arb[i][j] << "\n";
    */
    return 0;
}