#include<iostream>
#include<stdio.h>
#include<vector>
#include<set>
#include<string.h>

using namespace std;

struct edge
{
    int x, y, cost;
};

const int NMAX = 2e5 + 5, MMAX = 4e5 + 5;
int n, m, tata[NMAX], rank[NMAX], cheapest[NMAX], suma, culori[NMAX];
edge min_edge[NMAX];
vector<int> mst[NMAX];
vector<pair<int, int>> v[NMAX];

void citire()
{
    cin >> n >> m;
    int x, y, cost;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y >> cost;
        v[x].push_back({y, cost});
        v[y].push_back({x, cost});
    }
}

void dfs(int node, int culoare)
{
    if(culori[node])
        return;
    culori[node] = culoare;
    for(int i = 0; i < mst[node].size(); i++)
        dfs(mst[node][i], culoare);
}

void solve()
{
    set<pair<int, int>> s;
    int nr_culori = 0;
    for(int iter = 1; iter <= 30; iter++)
    {
        nr_culori = 0;
        memset(culori, 0, sizeof(culori));
        for(int j = 1; j <= n; j++)
        {
            if(!culori[j])
            {
                nr_culori++;
                dfs(j, nr_culori);
            }
        }
        if(nr_culori == 1)
            break;

        for(int i = 1; i <= nr_culori; i++)
            min_edge[i] = {-1, -1, 1030};

        for(int j = 1; j <= n; j++)
        {
            int col = culori[j];
            for(int k = 0; k < v[j].size(); k++)
            {
                int nod = v[j][k].first, cost = v[j][k].second;
                if(cost < min_edge[col].cost && col != culori[nod])
                {
                    min_edge[col] = {j, nod, cost};
                }
            }
        }

        for(int j = 1; j <= nr_culori; j++)
        {
            pair<int, int> nod = {min(min_edge[j].x, min_edge[j].y), max(min_edge[j].x, min_edge[j].y)};
            if(!s.count(nod))
            {
                s.insert({nod});
                mst[nod.first].push_back(nod.second);
                mst[nod.second].push_back(nod.first);
                suma = suma + min_edge[j].cost;
            }
        }
    }

    cout << suma << "\n" << n - 1 << "\n";

    for(auto nod : s)
    {
        cout << nod.first << " " << nod.second << "\n";
    }
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    citire();
    solve();
}