#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct Nod{
    int n;
    int w;
};

struct Muchie{
    int x,y,w;


};
bool operator < (const Muchie n, const Muchie m){
        return (n.w>m.w);
}
vector<vector<Nod>> L;
vector<int> Noduri_comp;

void citire(){
    int n,m;
    in>>n>>m;

    L.resize(n+1);
    Noduri_comp.resize(n+1);
    for(int i=1;i<n+1;i++){
        Noduri_comp[i] = i;
    }
    for(int i=0;i<m;i++){
        int x,y,w;
        in>>x>>y>>w;
        Nod tmp;
        tmp.n = y;
        tmp.w = w;
        L[x].push_back(tmp);
        tmp.n = x;
        tmp.w = w;
        L[y].push_back(tmp);
    }
}
void prim(){
    Muchie smallest;
    int cost_total = 0;
    vector<Muchie> rez;
    priority_queue<Muchie> pq;
    queue<int> q;
    vector<int> viz(L.size(),0);

    q.push(1);
    viz[1]=1;
    while(!q.empty()){
        int actual = q.front();
        q.pop();
        for(auto vecin : L[actual]){
            if(viz[vecin.n]==0){
                Muchie m;
                m.w=vecin.w;
                m.y=vecin.n;
                m.x=actual;
                pq.push(m);
            }
        }

        do{
            smallest=pq.top();
            pq.pop();
        }while(viz[smallest.y]!=0 && !pq.empty());
        if(viz[smallest.y]==0){
        rez.push_back(smallest);
        cost_total+=smallest.w;
        q.push(smallest.y);
        viz[smallest.y] = 1;
        }
    }
    out<<cost_total<<'\n';
    out<<rez.size()<<'\n';
    for(auto e:rez){
        out<<e.x<<' '<<e.y<<'\n';
    }

}





int main(){
    citire();
    prim();

}