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

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

vector<int > graph[NMAX], graphC[NMAX];
priority_queue <pair<int, pair <int, int> > > myheap;
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;
    graph[a].push_back(b);
    graphC[a].push_back(c);
    myheap.push(make_pair(-c, make_pair(a,b)));
}

}

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(make_pair(nod1,nod2));
            nrMuchii++;
            cost += (-best.first);
            unite(find_tata(nod1),find_tata(nod2));

        }
    }

}

void afisare(){
    g<< cost<<endl;
    g<< nrMuchii<<endl;
    for(int i = 0; i < nrMuchii ;i++)
        g<<graf[i].first<< " "<<graf[i].second<<endl;
}
int main()
{
    citire();
    Kruskal();
    afisare();
    return 0;
}