// Kruskal cu priority_queue
// 100 de puncte #592 pbinfo

#include <fstream>
#include <forward_list>
#include <bitset>
#include <queue>
#include <utility>

using namespace std;

const int MAX = 101;

int n,m,cost,G[MAX][MAX],sz;
forward_list<pair<int,int>>L;
bitset<MAX>viz;

void citire_date();
void kruskal(int nod_start);
void raspuns();

int main(){

    citire_date();
    kruskal(1);
    raspuns();
    return 0;
}

void citire_date(){

    ifstream fin("apm.in");
    int n1,n2,ct;

    fin>>n>>m;
    for(;m>0;--m){
        fin>>n1>>n2>>ct;
        G[n1][n2]=G[n2][n1]=ct;
    }

    fin.close();
}

void kruskal(int nod_start){

    //Tipul folosit este pair<int,pair<int,int>> -> un element E de acest tip are urmatoarele proprietati:
    //E.first este costul muchiei
    //E.second.first este primul nod din muchie
    //E.second.second este al doilea nod din muchie
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>Q;
    pair<int,pair<int,int>> E = {0,{0,nod_start}};
    int nod=nod_start;

    do{
        if(!viz[nod]){
            viz[nod]=1;
            cost+=E.first;
            if(E.second.first){
                L.push_front({E.second.first,E.second.second});
                ++sz;
            }
            for(int i=1;i<=n;++i){
                if(!G[nod][i] || viz[i])
                    continue;
                Q.push({G[nod][i],{nod,i}});
            }
        }
        E=Q.top();
        Q.pop();
        nod=E.second.second;
    }while(!Q.empty());
}

void raspuns(){

    ofstream fout("apm.out");

    fout<<cost<<'\n'<<sz<<'\n';
    for(auto& it:L)
        fout<<it.first<<' '<<it.second<<'\n';

    fout.close();
}