#include <bits/stdc++.h>
using namespace std;

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

/// STRUCTURES
struct edge
{
    int x, y, cost;

    edge()
    {
        x = y = -1;
        cost = 1024 * 1024 * 1024 + 7;
    }

    edge(int _x, int _y, int _cost)
    {
        x = _x; y = _y; cost = _cost;
    }
};

/// GLOBAL VARIABLES
const int NMAX = 2 * 1e5 + 5, MMAX = 4 * 1e5 + 5;
int nodes, edges, total_cost, total_nodes;
int color[NMAX];
edge min_edge[NMAX];
vector<pair<int,int>>graph[NMAX], mst[NMAX];
set<pair<int,int>>apm;

/// DFS PENTRU A COLORA COMPONENTELE CONEXE
inline void dfs(int curr_node, int curr_col)
{
    if(color[curr_node])
        return;

    color[curr_node] = curr_col;

    for(auto new_node : mst[curr_node])
        dfs(new_node.first, curr_col); 
}

int main()
{
    ios::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);

    fin >> nodes >> edges;

    for(int i = 1; i <= edges; ++ i)
    {
        int node1, node2, cost;
        fin >> node1 >> node2 >> cost;
        graph[node1].push_back({node2,cost});
        graph[node2].push_back({node1, cost});
    }

    for(int itr = 1; itr <= 50; ++ itr)
    {
        int col = 0;

        for(int i = 1; i <= nodes; ++ i)
            color[i] = 0;

        for(int i = 1; i <= nodes; ++ i)
        {
            if(!color[i])
            {
                col++;
                dfs(i, col);
            }
        }

        if(col == 1)
            break; /// AVEM SOLUTIE

        for(int i = 1; i <= col; ++ i)
            min_edge[i] = edge{};

        for(int i = 1; i <= nodes; ++ i)
        {
            for(auto node : graph[i])
            {
                int vec = node.first;
                int cost = node.second;
                int colo = color[i];

                if(cost < min_edge[colo].cost && color[vec] != color[i])
                {
                    min_edge[colo] = {i, vec, cost};
                }
            }
        }

        for(int i = 1; i <= col; ++ i)
        {
            int x = min_edge[i].x;
            int y = min_edge[i].y;
            int cost = min_edge[i].cost;

            pair<int,int>muc = {min(x,y), max(x, y)};

            if(apm.count(muc) > 0)
                continue;

            total_cost += cost;
            apm.insert(muc);

            mst[x].push_back({y, cost});
            mst[y].push_back({x, cost});
        }
    }

    fout << total_cost << '\n' << apm.size() << '\n';

    for(auto x : apm)
        fout << x.first << ' ' << x.second << '\n';

}