#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define N 200001

using namespace std;

bool visited[N];
int T[N]; //vectorul de tati
int S[N]; //vector de sizes
int cost_total;

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

struct Muchie{
    int x;
    int y;
    int cost;
};

vector<Muchie> muchii;
vector<Muchie> rezultat;

class Graph {
	
public:
	vector <int> adiacenta[N];
    int n_g, m_g;
    vector <int> componente[N];
    vector <int> solution;
    void addEdge_neorientat(int h, int t);
    void addEdge_orientat(int h, int t);
    void BFS_mininum_distances(int root);
	void DFS(int vf);
    void SolveSortTop(int n_g, int m_g);
    void Assign(int u, int root, vector<int> &conexitate);
    void CTC();
    void Sort_Muchie(vector<Muchie> v);
};
	
 
	
void Graph::addEdge_neorientat(int h,int t)
{
     adiacenta[h].push_back(t);
     adiacenta[t].push_back(h);
}

void Graph::addEdge_orientat(int h,int t)
{
     adiacenta[h].push_back(t);
}
 
	
void Graph::DFS(int vf)
{
	visited[vf] = true;
	
	for(int i = 0; i < adiacenta[vf].size(); ++i)
		if (!visited[adiacenta[vf][i]])
			DFS(adiacenta[vf][i]);
    
    solution.push_back(vf);
	
}

bool compareByCost(Muchie a, Muchie b)
{
    return a.cost < b.cost;
}

int find(int x){
    while (x != T[x]) {
        x = T[x];
        find(x);
    }
    return x;
}

void connect(int x, int y){
    int T_X = find(x), T_Y = find(y);
    
    if (S[T_X] >= S[T_Y]) {
        T[T_Y] = T_X;
        S[T_X] += S[T_Y];
	
    } else {
        T[T_X] = T_Y;
        S[T_Y] += S[T_X];
    }
	
}

void kruskal()
{
    for (auto muchie : muchii){
         if (find(muchie.x) != find(muchie.y)) {
            connect(muchie.x,muchie.y);
            cost_total += muchie.cost;
            rezultat.push_back({muchie.x,muchie.y,0});
            
        }
    }
}
	

	
int main()
{
	
	int n, M, n1, n2, conexe = 0, s = 2;

	//pb 2 fin >> n >> m >> s;

    fin>>n>>M;
	
	Graph g;

    g.n_g = n;
    g.m_g = M;
	
	Muchie m;
    for (int i = 0; i < M; i++)
	{
        fin>>m.x>>m.y>>m.cost;
        muchii.push_back(m);
    }
    

    sort(muchii.begin(), muchii.end(), compareByCost);
    
    for (int i=0; i<=n; i++) {
        T[i] = i;
        S[i] = 1;
    }
    
    kruskal();
	
    fout << cost_total << "\n" << rezultat.size() << "\n";
    
    for (int i = 0; i < rezultat.size(); i++)
    {
        fout<<rezultat[i].x<<' '<<rezultat[i].y<<endl;
    }
    
	return 0;
	
}