#include <iostream>
	
#include <fstream>
	
#include <vector>
	
#include <queue>
	
#include <algorithm>
	
#define N 200001
	
 
	
 
	
using namespace std;
	
 
	
	
	
class Graph {
	
	
	
public:
	
//structuri
	
    struct Muchie{
	
        int x;
	
        int y;
	
        int cost;
	
    };
	
//vectori 
	
	vector <int> adiacenta[N];
	
    vector <int> solution;
	
    vector<Muchie> muchii;
	
    vector<Muchie> rezultat;
	
 
	
//arrays
	
    bool visited[N];
	
    int T[N]; //vectorul de tati
	
    int S[N]; //vector de sizes
	
 
	
//variabile
	
    int cost_total = 0;
	
//functii
	
    void addEdge_neorientat(int h, int t);
	
    void addEdge_orientat(int h, int t);
	
	void DFS(int vf);
	
    void Solve_Conexe_DFS();
	
    void BFS_mininum_distances(int root, int n);
	
    void Solve_Min_Dist_BFS();
	
    void Solve_Sortaret();
	
    void Solve_APM();
	
    static bool compareByCost(Muchie a, Muchie b);
	
    int find(int x);
	
    void connect(int x, int y);
	
    void kruskal();
	
 
	
};
	
	
	
 
	
	
	
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);
	
	
	
}
	
 
	
void Graph::Solve_Conexe_DFS()
	
{
	
    ifstream fin("dfs.in");
	
    ofstream fout("dfs.out");
	
 
	
    int n, m, n1, n2, conexe = 0;
	
 
	
    fin>>n>>m;
	
 
	
    for (int i = 1; i <= m; i++)
	
    {
	
        fin >> n1 >> n2;
	
        addEdge_neorientat(n1,n2);
	
    }
	
 
	
    for(int i = 1; i <= n; i++){
	
        if (!visited[i])
	
        {
	
           conexe += 1;
	
           DFS(i);
	
        }
	
    }
	
 
	
    fout << conexe;
	
 
	
    fin.close();
	
}
	
 
	
 
	
void Graph::BFS_mininum_distances(int root, int n)
	
{
	
        ofstream fout("bfs.out");
	
 
	
        vector<int> d(n + 1, -1);
	
        queue<int> q;
	
	
	
        d[root] = 0;
	
        q.push(root);
	
	
	
        while (!q.empty()) {
	
            int current = q.front();
	
            q.pop();
	
 
	
            for (auto &index : adiacenta[current]) {
	
                if (d[index] == -1)
	
                {
	
                    d[index] = d[current] + 1;
	
                    q.push(index);
	
                }
	
            }
	
 
	
        }
	
	
	
        for (int i = 1; i <= n; ++i) {
	
            fout << d[i] << ' ';
	
        }
	
}
	
 
	
void Graph::Solve_Min_Dist_BFS()
	
{
	
    ifstream fin("bfs.in");
	
 
	
    int n, m, n1, n2, s;
	
 
	
    fin>>n>>m>>s;
	
 
	
 
	
    for (int i = 1; i <= m; i++)
	
	{
	
        fin >> n1 >> n2;
	
        addEdge_orientat(n1,n2);
	
    }
	
 
	
    BFS_mininum_distances(s, n);
	
 
	
    fin.close();
	
}
	
 
	
void Graph::Solve_Sortaret()
	
{
	
    ifstream fin("sortaret.in");
	
    ofstream fout("sortaret.out");
	
 
	
    int n, m, n1, n2;
	
 
	
    fin>>n>>m;
	
    
	
    for (int i = 1; i <= m; i++)
	
	{
	
        fin >> n1 >> n2;
	
        addEdge_orientat(n1,n2);
	
    }
	
    
	
    for (int i = 1; i <= n; ++i)
	
    {
	
        if (!visited[i])
	
            DFS(i);
	
    }
	
	
	
	
	
    int upper_limit = solution.size() - 1;
	
	
	
    for (int i = upper_limit; i > -1; i--)
	
         fout << solution[i] << ' ';
	
 
	
    fin.close();
	
}
	
 
	
bool Graph::compareByCost(Muchie a, Muchie b)
	
{
	
    return a.cost < b.cost;
	
}
	
 
	
int Graph::find(int x){
	
    while (x != T[x]) {
	
        x = T[x];
	
        find(x);
	
    }
	
    return x;
	
}
	
 
	
void Graph::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 Graph::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});
	
            
	
        }
	
    }
	
}
	
void Graph::Solve_APM()
	
{
	
    ifstream fin("apm.in");
	
    ofstream fout("apm.out");
	
 
	
    int n, M, n1, n2;
	
    fin>>n>>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;
	
    }
	
 
	
    fin.close();
	
 
	
}
	
 
	
int main()
	
{
	
    Graph g;
	
    
	
    //tema 1: DFS
	
    // g.Solve_Conexe_DFS();
	
 
	
    //tema 1: BFS
	
    //g.Solve_Min_Dist_BFS();
	
 
	
    //tema 1: Sortaret
	
    //g.Solve_Sortaret();
	
 
	
    //tema2: Apm
	
    g.Solve_APM();
	
 
	
    return 0;
	
}