#include <bits/stdc++.h>

std :: ifstream in ("apm.in");

std :: ofstream out ("apm.out");

const int NMAX = 2e5 + 5;

int n;

int m;

int x;

int y;

int d;

int sum;

int rank[NMAX];

int parent[NMAX];

std :: vector <std :: pair <int, std :: pair <int, int>>> v;

std :: stack <std :: pair <int, int>> ans;

int getroot(int x)
{
    if(parent[x] == x)
    {
        return x;
    }

    parent[x] = getroot(parent[x]);

    return parent[x];
}

int main()
{

    in >> n >> m;

    for(int i = 1; i <= m; i ++)
    {
        in >> x >> y >> d;

        v.push_back(std :: make_pair(d, std :: make_pair(x, y)));
    }

    for(int i = 1; i <= n; i ++)
    {
        parent[i] = i;
    }

    std :: sort(v.begin(), v.end());

    std :: reverse(v.begin(), v.end());

    /*for(auto i : v)
    {
        std :: cout << i.first << " ";
    }*/

    n --;

    while(n)
    {
        d = v.back().first;

        x = v.back().second.first;

        y = v.back().second.second;

        int aux = getroot(x);

        int aux1 = getroot(y);

        if(aux != aux1)
        {
            ans.push(std :: make_pair(x, y));

            if(rank[aux] > rank[aux1])
            {
                parent[aux1] = aux;
            }
            else if(rank[aux] < rank[aux1])
            {
                parent[aux] = aux1;
            }
            else
            {
                parent[aux1] = aux;

                rank[aux] ++;
            }

            sum += d;

            n --;
        }

        v.pop_back();
    }

    out << sum << '\n';

    out << ans.size() << '\n';

    while(!ans.empty())
    {
        out << ans.top().first << " " << ans.top().second << '\n';

        ans.pop();
    }

    return 0;
}