#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

const int MAXN = 200000 + 5;

using namespace std;

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

typedef pair<pair<int,int>,int > pii;

vector<pair<int,int> >graf[MAXN];
priority_queue<pii,vector<pii>, greater<pii> >coada;
bool viz[MAXN];
int n,m;

int main()
{

    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int x,y,cost;
        in>>x>>y>>cost;
        graf[x].push_back({cost,y});
        graf[y].push_back({cost,x});
    }
    viz[1] = true;
    for(int i = 0; i < graf[1].size(); i++){
        coada.push({graf[1][i],1});
    }
    int cost_minim = 0;
    vector<pair<int,int> >arbore;
    while(coada.size()){

        int cost = coada.top().first.first;
        int tata = coada.top().second, nod = coada.top().first.second;
        //if(tata == 9)
            //out<<"UF";
        coada.pop();
        if(viz[nod])
            continue;
        arbore.push_back({tata,nod});
        viz[nod] = true;
        cost_minim += cost;

        for(int i = 0; i < graf[nod].size(); i++){
            int curent = graf[nod][i].second;
            if(!viz[curent]){
                coada.push({graf[nod][i],nod});
            }

        }
    }
    out<<cost_minim<<"\n"<<arbore.size()<<"\n";
    for(auto muchie : arbore)
        out<<muchie.first<<" "<<muchie.second<<"\n";
    return 0;
}