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

ifstream f("apm.in");
ofstream g("apm.out");
#define NMAX 200003
int n, m, nrMuchii, cost;

vector<int > graph[NMAX], graphC[NMAX];
priority_queue <pair<int, pair <int, int> > > myheap;

///rang[i] nr de noduri din arborele cu radacina i, initial 1;
int rang[NMAX], tata[NMAX];
vector<pair<int,int> > graf;

void citire(){
f>>n>>m;

for(int i = 0; i < m ; i ++)
{
    int a,b,c;
    f>>a>>b>>c;
    myheap.push({-c, {a,b}});
    myheap.push({-c, {b,a}});
}

}
/// unim arborele mai mic cu cel mare
void unite(int x, int y){
    if(rang[x]< rang[y])
    {
        tata[x] = y;
        rang[y] += rang[x];
    }
    else {
        tata[y] = x;
        rang[x] += rang[y];
    }
}

int find_tata(int node){
    if(tata[node] == node)
        return node;

int ans = find_tata(tata[node]);
tata[node] = ans;
return ans;
}

void Kruskal(){
    for(int i = 1; i <= n; i ++)
       {
        rang[i] = 1;
        tata[i] = i;
       }

    while(!myheap.empty()){
        pair<int, pair <int, int> > best = myheap.top();
        myheap.pop();

        int nod1 = best.second.first;
        int nod2 = best.second.second;

        if(find_tata(nod1) != find_tata(nod2))
        {
            graf.push_back({nod1,nod2});
            cost += (-best.first);
            unite(find_tata(nod1),find_tata(nod2));

        }
    }
}

void afisare(){
    g<< cost<<'\n';
    g<< n-1<<'\n';
    for(int i = 0; i < n-1 ;i++)
        g<<graf[i].first<< " "<<graf[i].second<<'\n';
}
int main()
{
    citire();
    Kruskal();
    afisare();
    return 0;
}