#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <set>

using namespace std;
using ll = long long;
const int NMAX = 2e5;
const ll INF = 1e18;
vector<pair<int , int> > adj[NMAX+1];
vector<pair<int , int> > mst[NMAX+1];
int color[NMAX+1];


struct edge {
    int x, y;
    ll cost;
    edge () {
        x = -1 , y = -1 , cost = INF;
    }
    edge(int _x, int _y, int _cost) {
        x = _x; y = _y; cost = _cost;
    }
} min_edge[NMAX+1];

void dfs (int nod , int col)
{
    if (color[nod] != 0) return;
    color[nod] = col;
    for (auto &ed : mst[nod])
    {
        int to = ed.first;
        dfs(to , col);
    }
}

int main ()
{
    freopen("apm.in" , "r" , stdin);
    freopen("apm.out" , "w" , stdout);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c; cin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }

    set<pair<int , int> > added_edges;
    ll cost_MST = 0;

    for (int it = 0; it < 50; it++)
    {
        for (int i = 1; i <= n; i++)
        {
            color[i] = 0;
        }
        int colors = 0;

        for (int nod = 1; nod <= n; nod++)
        {
            if (color[nod] == 0) {
                dfs (nod , ++colors);
            }
        }

        if (colors == 1) break;

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

        for (int i = 1; i <= n; i++)
        {
            for (auto ed : adj[i])
            {
                int to = ed.first;
                int cost = ed.second;
                int col = color[i];

                if (cost < min_edge[col].cost && color[i] != color[to])
                {
                    min_edge[col] = edge(i , to , cost);
                }
            }
        }

        for (int i = 1; i <= n; i++)
        {
            edge add_edge = min_edge[i];
            int x = add_edge.x , y = add_edge.y , cost = add_edge.cost;

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

            if (added_edges.count(muchie) > 0) continue;

            mst[x].push_back({y, cost});
            mst[y].push_back({x, cost});
            cost_MST += cost;
            added_edges.insert(muchie);
        }
    }
    cout << cost_MST << '\n';
    cout << n - 1 << '\n';
    for (auto &ed : added_edges)
    {
        cout << ed.first << ' ' << ed.second << '\n';
    }
}