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

using namespace std;

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

const int Nmax=200001, inf=10001;

int N, M, sum;
vector<pair<int, int>> ad[Nmax];
vector<pair<int, int>> apm;

struct muchie{
    int s, f, c;
};
struct cmp{
    bool operator()(muchie a, muchie b){
        return a.c>b.c; 
        // pentru ca ne dorim costul minim si nu maxim
    }
};
priority_queue<muchie, vector<muchie>, cmp> pq;

bool vis[Nmax];

void adaugare_vecini(int nod){
    for (auto it:ad[nod])
        if (vis[it.first]==0){
            pq.push({nod, it.first, it.second});
        }
}

int main (){
    fin>>N>>M;

    int x, y, c;
    for (int i=0; i<M; i++){
        fin>>x>>y>>c;
        ad[x].push_back({y, c});
        ad[y].push_back({x, c});
    }

    // Algortimul lui Prim
    vis[1]=1;
    adaugare_vecini(1);
    while (!pq.empty()){
        muchie crt=pq.top();
        pq.pop();

        if (vis[crt.f]==0){
            vis[crt.f]=1;
            apm.push_back({crt.s, crt.f});
            sum+=crt.c;
            adaugare_vecini(crt.f);
        }
    }

    fout<<sum<<'\n';
    fout<<apm.size()<<'\n';
    for (auto it:apm)
        fout<<it.first<<' '<<it.second<<'\n';

    return 0;
}