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

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

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

void cuplam(int x,int y){
    daddy[daddy[x]] = daddy[y];
    ans.push_back(make_pair(x,y));
    ///Arb[x].push_back(y);
    ///Arb[y].push_back(x);
}

int whos_your_daddy(int x){ /// compactarea lantului
    if(daddy[x] != x)
        daddy[x] = whos_your_daddy(daddy[x]);
    return daddy[x];
}

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(whos_your_daddy(x) == whos_your_daddy(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;
}