//  --------------------------------------------------------
// BFS

//#include <iostream>
//#include <fstream>
//
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//
//ifstream f("bfs.in");
//ofstream g("bfs.out");
//vector<vector<int>> lista;
//queue<int> q;
//vector<int> distanta;
//
//int main()
//{
//    int n,m,s;
//    f >> n >> m >> s;
//    int x,y ;
//    lista.resize(n+1);
//    distanta.resize(n+1,-1);
//    q.push(s);
//    distanta[s] = 0;
//    while(f >> x >> y)
//    {
//        lista[x].push_back(y);
//    }
//    while(!q.empty())
//    {
//        int curr = q.front();
//        q.pop();
//        for(auto vecin : lista[curr]){
//            if(distanta[vecin] == -1){
//                distanta[vecin] = distanta[curr] + 1;
//                q.push(vecin);
//            }
//        }
//    }
//
//    for(int i = 1; i<=n ;i++)
//        g << distanta[i] << ' ' ;
//
//    return 0;
//}

// -----------------------------------------------------------------------------
// DFS
//
//#include <iostream>
//#include <fstream>
//#include <vector>
//
//using namespace std;
//
//int n,m;
//
//ifstream f("dfs.in");
//ofstream g("dfs.out");
//
//vector<vector<int>> lista;
//vector<bool> verif;
//
//void dfs(int nod)
//{
//    if(verif[nod])return;
//    verif[nod] = true;
//    for(auto vecin: lista[nod])
//    {
//        dfs(vecin);
//    }
//}
//
//int main()
//{
//    int x,y;
//    f >> n >> m;
//    lista.resize(n+1,{});
//    verif.resize(n+1, false);
//    while(f >> x >> y)
//    {
//        lista[x].push_back(y);
//        lista[y].push_back(x);
//    }
//
//    int nrComp = 0;
//    for(int i = 1; i<=n; i++)
//    {
//        if(!verif[i])
//        {
//            nrComp++;
//            dfs(i);
//        }
//    }
//
//    g << nrComp;
//
//    f.close();
//    g.close();
//
//    return 0;
//}

// ----------------------------------------
// Bipartit

//
//#include <iostream>
//#include <vector>
//#include <queue>
//
//using namespace std;
//
//int n,m;
//vector<vector<int>> lista ;
//vector<int> bipartit;
//queue<int> q;
//
//int main()
//{
//    int x, y;
//    cin >> n >> m;
//    lista.resize(n+1,{});
//    for(int i=1; i<=m ; i++){
//        cin >> x >> y;
//        lista[x].push_back(y);
//        lista[y].push_back(x);
//    }
//    bipartit.resize(n+1, 0);
//    bool turn = true;
//
//    for(int i = 1; i<=n ; i++)
//    {
//        if(bipartit[i] == 0)
//        {
//            turn = true;
//            q.push(i);
//            while(!q.empty())
//            {
//                int size = q.size();
//                while(size)
//                {
//                    int curr = q.front();
//                    q.pop();
//                    if(turn)
//                        bipartit[curr] = 1;
//                    else{
//                        bipartit[curr] = 2;
//                    }
//                    for(auto vec : lista[curr])
//                        if(bipartit[vec] == bipartit[curr])
//                        {
//                            cout << "IMPOSSIBLE";
//                            return 0;
//                        }
//                        else if(bipartit[vec] == 0){
//                            q.push(vec);
//                        }
//                        size--;
//                }
//                turn = !turn;
//
//            }
//        }
//    }
//
//    for (int i = 1; i<=n ;i++)
//        cout << bipartit[i] << ' ';
//
//    return 0;
//}

// --------------------------------------------------------------------------------------
// Sortare topologica
//#include <iostream>
//#include <vector>
//#include <queue>
//using namespace std;
//int n,m;
//vector<vector<int>> lista;
//vector<int> verif;
//vector<int> raspuns;
//vector<int> gradIn;
//queue<int> q;
//
//int main()
//{
//    int x,y;
//    int contor = 0;
//    cin >> n >> m;
//    lista.resize(n+1, {});
//    verif.resize(n+1,0);
//    gradIn.resize(n+1,0);
//    for(int i = 1 ; i<=m ; i++){
//        cin >> x >> y;
//        lista[x].push_back(y);
//        gradIn[y]++;
//    }
//    for(int i = 1 ; i<=n; i++)
//        if(gradIn[i] == 0)
//            q.push(i);
//
//    while (!q.empty())
//    {
//        int curr = q.front();
//        q.pop();
//        raspuns.push_back(curr);
//        verif[curr] = 1;
//        contor++;
//        for(auto vec : lista[curr])
//        {gradIn[vec]--; if (gradIn[vec] == 0)q.push(vec);}
//    }
//    if(contor != n)
//    {
//        cout << "IMPOSSIBLE";
//    }
//    else
//        for(auto el : raspuns)
//            cout << el << ' ';
//
//    return  0;
//}
//// FILL
//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//char mat[1001][1001];
//bool visited[1001][1001];
//int n, m;
//
//int counter;
//
//void fill(int i, int j)
//{
//    if(mat[i][j] != '.')return;
//    if(visited[i][j]) return;
//    if(i<1 || i > n)return;
//    if(j<1 || j >m)return;
//
//    visited[i][j] = true;
//
//    fill(i+1,j);
//    fill(i,j+1);
//    fill(i,j-1);
//    fill(i-1,j);
//}
//
//int main()
//{
//    cin >> n >> m;
//    for(int i = 1; i<= n ; i++)
//    {
//        for(int j = 1; j <= m; j++)
//        {
//            cin >> mat[i][j];
//        }
//    }
//
//    for(int i = 1; i<=n; i++)
//    {
//        for(int j = 1; j<=m ; j++)
//        {
//            if(!visited[i][j] && mat[i][j] == '.')
//            {
//                counter++;
//                fill(i,j);
//            }
//        }
//    }
//
//    cout << counter;
//
//    return 0;
//}
// Tarjan / Submerge
//#include <iostream>
//#include <vector>
//#include <queue>
//#include <cstring>
//using namespace std;
//
//int n, m;
//int x, y;
//int discovery[10005], low[10005], parent[10005];
//int visited[10005];
//int timer = 0;
//
//bool articulation[10005];
//vector<int> lista[10005];
//
//void dfs(int node) {
//    visited[node] = 1;
//    discovery[node] = low[node] = ++timer;
//    int children = 0;
//
//    for (int neighbor : lista[node]) {
//        if (!visited[neighbor]) {
//            children++;
//            parent[neighbor] = node;
//
//            dfs(neighbor);
//
//            low[node] = min(low[node], low[neighbor]);
//
//            // Check if node is an articulation point
//            if (parent[node] == -1 && children > 1) {
//                articulation[node] = true;
//            }
//            if (parent[node] != -1 && low[neighbor] >= discovery[node]) {
//                articulation[node] = true;
//            }
//        } else if (neighbor != parent[node]) {
//            low[node] = min(low[node], discovery[neighbor]);
//        }
//    }
//}
//
//void solveSubmerge() {
//    timer = 0;
//    memset(discovery, 0, sizeof(discovery));
//    memset(low, 0, sizeof(low));
//    memset(parent, -1, sizeof(parent));
//    memset(articulation, false, sizeof(articulation));
//    memset(visited, 0, sizeof(visited));
//
//    for (int i = 1; i <= m; i++) {
//        cin >> x >> y;
//        lista[x].push_back(y);
//        lista[y].push_back(x);
//    }
//
//    // Perform DFS for all nodes to handle disconnected graphs
//    for (int i = 1; i <= n; i++) {
//        if (!visited[i]) {
//            dfs(i);
//        }
//    }
//
//    int answer = 0;
//    for (int i = 1; i <= n; i++) {
//        if (articulation[i]) {
//            answer++;
//        }
//    }
//
//    cout << answer << '\n';
//
//    // Clear graph for next test case
//    for (int i = 1; i <= n; i++) {
//        lista[i].clear();
//    }
//}
//
//int main() {
//    cin >> n >> m;
//    while (n != 0 && m != 0) {
//        solveSubmerge();
//        cin >> n >> m;
//    }
//    return 0;
//}
//// Padure/ Lee
//#include <bits/stdc++.h>
//
//using namespace std;
//
//ifstream fin("padure.in");
//ofstream fout("padure.out");
//
//const int N = 1005;
//int n, m, a[N][N], b[N][N], xs, ys, xf, yf;
//
//pair<int, int> dir[4] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
//deque<pair<int, int>> Q;
//
//bool inmat(int, int);
//void lee(int, int);
//
//int main()
//{
//    fin >> n >> m;
//    fin >> xs >> ys >> xf >> yf;
//    for(int i = 1; i <= n; ++i)
//        for(int j = 1; j <= m; ++j)
//            fin >> a[i][j], b[i][j] = INT_MAX;
//    lee(xs, ys);
//    fout << b[xf][yf];
//    return 0;
//}
//
//bool inmat(int i, int j)
//{
//    return i >= 1 && i <= n && j <= m && j >= 1;
//}
//
//void lee(int xs, int ys)
//{
//    b[xs][ys] = 0;
//    Q.push_front({xs, ys});
//    while(!Q.empty())
//    {
//        int x = Q.front().first;
//        int y = Q.front().second;
//        Q.pop_front();
//        for(int d = 0; d < 4; ++d)
//        {
//            int i = x + dir[d].first;
//            int j = y + dir[d].second;
//            if(inmat(i, j))
//            {
//                int pret = b[x][y] + (a[i][j] != a[x][y] ? 1 : 0);
//                if(pret < b[i][j])
//                {
//                    b[i][j] = pret;
//                    if(!Q.empty() && b[i][j] <= b[Q.front().first][Q.front().second])
//                        Q.push_front({i, j});
//                    else
//                        Q.push_back({i, j});
//                }
//            }
//        }
//    }
//}

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

ifstream f("apm.in");
ofstream g("apm.out");

int n, m;
priority_queue<pair<int, pair<int, int>>> muchii;

int x, y, z;
vector<int> parents;

vector<pair<int, int>> apm;
int cost = 0;

int whoParent(int x) {
    if (parents[x] != x)
        parents[x] = whoParent(parents[x]);  // Path compression
    return parents[x];
}

bool Union(int x, int y) {
    int parentX = whoParent(x);
    int parentY = whoParent(y);

    if (parentX == parentY)  // Already in the same set
        return false;

    parents[parentY] = parentX;  // Union by rank can be added here
    return true;
}

int main() {
    f >> n >> m;

    parents.resize(n + 1);
    for (int i = 1; i <= n; i++)
        parents[i] = i;

    for (int i = 1; i <= m; i++) {
        f >> x >> y >> z;
        muchii.push({-z, {x, y}});  // Cost negativ pentru sortare crescătoare
    }

    while (!muchii.empty()) {
        pair<int, pair<int, int>> curr = muchii.top();
        muchii.pop();

        if (Union(curr.second.first, curr.second.second)) {
            cost += -curr.first;  // Reversăm semnul pentru costul real
            apm.push_back(curr.second);
        }

        if (apm.size() == n - 1)  // Gata când avem n-1 muchii
            break;
    }

    g << cost << '\n';
    g << apm.size() << '\n';
    for (auto elem : apm) {
        g << elem.first << ' ' << elem.second << '\n';
    }

    return 0;
}