//We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people,
//and they should not go into the same group.
//Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi,
//return true if it is possible to split everyone into two groups in this way.
// Mai pe scurt acesta este un BFS putin diferit
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 2001;
//int n, m;
//bool isBipartite;
//int adj[MAX][MAX], viz[MAX];
//queue<int> q;
//
//void BFS(){
//    q.push(1);
//    viz[1] = 1;
//    while(!q.empty()){
//        int aux = q.front();
//        q.pop();
//        for(int i = 1; i <= n; i++){
//            if(viz[aux] == viz[i] && adj[aux][i] == 1){
//                isBipartite = false;
//                return;
//            }
//            else if(adj[aux][i] == 1 && viz[i] == 0){
//                q.push(i);
//                if(viz[aux] == 1){
//                    viz[i] = 2;
//                }
//                else{
//                    viz[i] = 1;
//                }
//            }
//        }
//    }
//}
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x][y] = adj[y][x] = 1;
//    }
//    isBipartite = true;
//    BFS();
//    if(!isBipartite){
//        fout << "False" << endl;
//    }
//    else{
//        fout << "True" << endl;
//        for(int i = 1; i <= n; i++){
//            if(viz[i] == 1){
//                fout << i << ' ';
//            }
//        }
//        fout<<endl;
//        for(int i = 1; i <= n; i++){
//            if(viz[i] == 2){
//                fout << i << ' ';
//            }
//        }
//        fout<<endl;
//    }
//
//    return 0;
//}
//

//One of the most popular algorithms for traversing a graph is the Depth First Search (DFS).
//The DFS is usually implemented as a recursive function. First we call the function for the starting node.
//For each call, we go through the adjacency list of the current node, and recursively call the function for the unvisited neighbours.
//Notice that if we permute the adjacency lists of the nodes, the order in which we visit them might differ.
//In this problem you are given a graph with N nodes and M edges and a permutation P of size N.
//If you are allowed to shuffle the adjacency lists, is it possible to visit the nodes during a DFS starting in node
//1 in the order given by P?
//Mai pe scurt acesta este un DFS care are o sortare in fiecare lista de adiacenta!
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 3;
//int n, m;
//vector<int> adj[MAX], dfs_order;
//int ord[MAX], viz[MAX];
//
//
//int compara(int a, int b){
//    return ord[a] < ord[b];
//}
//
//void DFS(int node){
//    viz[node] = 1;
//    dfs_order.push_back(node);
//    for(auto vecin : adj[node]){
//        if(viz[vecin] == 0){
//            DFS(vecin);
//        }
//    }
//}
//
//int main() {
//
//    fin >> n >> m;
//    vector<int> permutare(n);
//    for(int i = 1; i <= n; i++){
//        int aux;
//        fin >> aux;
//        ord[aux] = i;
//        permutare[i - 1] = aux;
//    }
//
//
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x].push_back(y);
//        adj[y].push_back(x);
//    }
//    for(int i = 1; i <= n; i++){
//        sort(adj[i].begin(), adj[i].end(), compara);
//    }
//
//    DFS(1);
// //    fout << "dfs_order : " << endl;
// //    for(int i = 0; i < n ; i++){
// //        fout << dfs_order[i] << ' ';
// //    }
// //    fout << endl << "permutare : \n";
// //    for(int i = 0; i < n; i++){
// //        fout << permutare[i] << ' ';
// //    }
//    fout << (permutare == dfs_order) << endl;
//
//    return 0;
//}

//There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where
//prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
//For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
//Return the ordering of courses you should take to finish all courses. If there are many valid answers,
//return any of them. If it is impossible to finish all courses, return an empty array.
//
//Problema cu cursurile adica un graf orientat in care trebuie sa aflam daca avem ciclu sau nu. Nu e terminata aici.


//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//const int MAX = 1e4 + 1;
//int n, m;
//vector<int> adj[MAX], viz, cur_path, rezultat;
//vector<int> DFS(int node){
//
//    if(viz[node]){
//        return {};
//    }
//    if(cur_path[node]){
//        return {node};
//    }
//
//    viz[node] = 1;
//    cur_path[node] = 1;
//    for(auto vecin : adj[node]){
//        vector<int> ciclu = DFS(vecin);
//        if(!ciclu.empty()){
//            return ciclu;
//        }
//    }
//    cur_path[node] = 0;
//    rezultat.push_back(node);
//    return {};
//}
//
//int main() {
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[y].push_back(x);
//    }
//    int ans = 1;
//    for(int i = 1; i <= n; i++){
//        if(!viz[i]){
//            vector<int> ciclu = DFS(i);
//            if(!ciclu.empty()){
//                ans = 0;
//            }
//        }
//    }
//
//
//    return 0;
//}


//Componente tare conexe
//        Se dă un graf orientat G = (V, E). O componentă tare conexă a grafului orientat G este o mulţime maximală de vârfuri U inclusă în V,
//        astfel încât, pentru fiecare pereche de vârfuri u şi v din U avem atât drum de la u la v cât şi drum de la v la u. Cu alte cuvinte,
//        vâfurile u şi v sunt accesibile unul din celălalt.
//
//Cerinţă
//        Dându-se un graf orientat G = (V, E) se cere să se determine componentele sale tare conexe.
//
//Date de intrare
//        Fişierul de intrare ctc.in conţine pe prima linie două numere naturale N si M ce reprezintă numărul de noduri din G şi
//        numărul muchiilor. Pe următoarele M linii se vor afla câte două numere naturale x şi y, separate prin spaţiu, reprezentând muchia orientată (x, y).
//
//Date de ieşire
//        În fişierul de ieşire ctc.out se va afişa pe prima linie un singur număr reprezentând numărul componentelor tare conexe.
//        Pe fiecare din următoarele linii se va scrie câte o componentă tare conexă prin enumerarea nodurilor componente.
//        Acestea pot fi afişate în orice ordine.
//
//
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("ctc.in");
//ofstream fout("ctc.out");
//
//const int MAX = 1e5 + 1, NEVIZITAT = -1;
//
//int n, m, id, sccCount, ids[MAX], low[MAX];
//vector<int> adj[MAX], cur_path[MAX];
//stack<int> stiva;
//vector<bool> onStack(MAX, false);
//
//
//void DFS(int node){
//
//    onStack[node] = true;
//    stiva.push(node);
//    ids[node] = low[node] = id++;
//
//    for(auto vecin : adj[node]){
//        if(ids[vecin] == NEVIZITAT){
//            DFS(vecin);
//        }
//
//        if(onStack[vecin]){
//            low[node] = min(low[node], low[vecin]);
//        }
//    }
//
//    if(low[node] == ids[node]){
//        while(!stiva.empty()){
//            int aux = stiva.top();
//            stiva.pop();
//            cur_path[sccCount].push_back(aux);
//            onStack[aux] = false;
//            low[aux] = ids[node];
//            if(aux == node){
//                break;
//            }
//        }
//        sccCount++;
//    }
//
//
//}
//
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x].push_back(y);
//    }
//
//    for(int i = 1; i <= n; i++){
//        ids[i] = NEVIZITAT;
//    }
//
//    for(int i = 1; i <= n; i++){
//        if(ids[i] == NEVIZITAT){
//            DFS(i);
//        }
//    }
//
//    fout << sccCount << endl;
//    for(int i = 0 ; i < sccCount; i++){
//        for(auto cmp : cur_path[i]){
//            fout << cmp << ' ';
//        }
//        fout << endl;
//    }
//    return 0;
//}

//5. Se dă o rețea neorientată cu n noduri și o listă de noduri reprezentând puncte de control pentru
//rețea în fișierul graf.in, în formatul precizat la începutul laboratorului; în plus, pe ultima linie din
//fișier se află punctele de control separate prin spațiu. Să se determine pentru fiecare nod din rețea
//distanța până la cel mai apropiat punct de control de acesta. În fișierul graf.out se vor afișa pentru
//fiecare nod de la 1 la n aceste distanțe separate prin spațiu.

//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("graf.in");
//ofstream fout("graf.out");
//
//const int MAX = 1e5 + 1;
//int n, m, control, viz[MAX], dist[MAX];
//vector<int> adj[MAX];
//queue<int> q;
//
//
//void BFS(int node){
//    q.push(node);
//    viz[node] = 1;
//    dist[node] = 0;
//
//    while(!q.empty()){
//        int nod = q.front();
//
//        q.pop();
//        for(auto vecin : adj[nod]){
//            if(!viz[vecin]){
//                q.push(vecin);
//                if(dist[vecin] > dist[nod] + 1 && dist[vecin] != 0){
//                    dist[vecin] = dist[nod] + 1;
//                }
//                viz[vecin] = 1;
//            }
//        }
//    }
//}
//
//
//int main() {
//
//    fin >> n >> m;
//    for(int i = 1; i <= m; i++){
//        int x, y;
//        fin >> x >> y;
//        adj[x].push_back(y);
//        adj[y].push_back(x);
//    }
//    fin >> control;
//
//    for(int i = 1; i <= n; i++) {
//        dist[i] = MAX;
//    }
//    for(int i = 1; i <= control; i++){
//        int pct;
//        fin >> pct;
//        for(int i = 1; i <= n; i++){
//            viz[i] = 0;
//        }
//        BFS(pct);
//    }
//    for(int i = 1; i <= n; i++){
//        fout << dist[i] << ' ';
//    }
//
//    return 0;
//}

// In cazul in care am nevoie de sort adj cu pair
//vector<pair<int, int>> adj[10001];
//
////...
//
//// Sortează vectorul de perechi la indexul x în funcție de cost (al doilea element al perechii)
//sort(adj[x].begin(), adj[x].end(), [](const pair<int, int>& a, const pair<int, int>& b) {
//return a.second < b.second;
//});

#include <bits/stdc++.h>

using namespace std;

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

const int MAX = 2e5 + 1;
int n, m, tata[MAX], inaltime[MAX], ok;
pair<int, int> final[MAX];

struct muchie{
    int x, y, cost;
}adj[2 * MAX];

int compara(muchie a, muchie b){
    return a.cost < b.cost;
}

int cauta(int a){
    if(tata[a] == a){
        return a;
    }
    return cauta(tata[a]);
}

int uneste(int a, int b){
    int nod1 = cauta(a);
    int nod2 = cauta(b);
    if(nod1 != nod2){
        if(inaltime[nod1] > inaltime[nod2]){
            tata[nod2] = nod1;
        }
        else if(inaltime[nod2] > inaltime[nod1]){
            tata[nod1] = nod2;
        }
        else{
            tata[nod1] = nod2;
            inaltime[nod2]++;
        }
    }
}

int main() {

    fin >> n >> m;

    for(int i = 1; i <= m; i++){
        fin >> adj[i].x >> adj[i].y >> adj[i].cost;
    }

    sort(adj + 1, adj + m + 1, compara);

    for(int i = 1; i <= n; i++){
        tata[i] = i;
        inaltime[i] = 1;
    }
    int sum = 0;
    for(int i = 1; i <= m; i++){
        int nod1 = cauta(adj[i].x);
        int nod2 = cauta(adj[i].y);
        if(nod2 != nod1){
            uneste(nod1, nod2);
            final[++ok].first = adj[i].x;
            final[ok].second = adj[i].y;
            sum += adj[i].cost;
        }
    }
    fout << sum << endl;
    fout << ok << endl;
    for(int i = 1; i <= ok; i++){
        fout << final[i].first << ' ' << final[i].second << endl;
    }
    return 0;
}