#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nMax 200005

using namespace std;
int n, m, sMin, nr;
typedef struct {
  int x, y, cost;
} muchie;
typedef struct {
  int x, y;
} result;
typedef struct {
  int rad, hMax;
} nod;
muchie edge;
result new_edge;
nod node[nMax];
vector <muchie> Edges;
vector <int> v[nMax];
vector <result> sol;

int comp(muchie x, muchie y){
 return x.cost < y.cost;
}
void read()
{
    ifstream fin("apm.in");
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        fin >> edge.x >> edge.y >> edge.cost;
        Edges.push_back(edge);
    }
    for(int i = 1; i <= n; ++i)
        node[i].rad = i, node[i].hMax = 0;
}
void dfs(int x, int y){
     for(int i = 0; i < v[x].size(); ++i){
        node[v[x][i]].rad = y;
        dfs(v[x][i], y);
     }
}
void solve(int x, int y)
{
    if(node[x].hMax < node[y].hMax)
        swap(x, y);
    v[x].push_back(y);
    node[x].hMax = max(node[x].hMax, node[y].hMax + 1);
    node[y].rad = x;
    dfs(y, x);
}
void apm()
{
    sort(Edges.begin(), Edges.end(), comp);
    for(int i = 0; i < Edges.size(); ++i){
        if(node[Edges[i].x].rad != node[Edges[i].y].rad){
            solve(node[Edges[i].x].rad, node[Edges[i].y].rad);
            sMin += Edges[i].cost;
            new_edge.x = Edges[i].x;
            new_edge.y = Edges[i].y;
            sol.push_back(new_edge);
             nr++;
            if(nr == n - 1) break;
        }
    }
}
void write()
{
    ofstream fout("apm.out");
    fout << sMin << "\n" << nr << "\n";
    for(int i = 0; i < nr; ++i)
        fout << sol[i].x << ' ' << sol[i].y << '\n';

}
int main()
{
    read();
    apm();
    write();
    return 0;
}