#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 200000
using namespace std;

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

int n, m;
int daddy[nmax + 1], rang[nmax + 1];

vector < pair < int, int > > sol;

struct kruskal
{
    int a, b, c;
};

kruskal muc[nmax * 2 + 5];

bool sortare(kruskal m1, kruskal m2)
{
    return (m1.c < m2.c);
}

int Root(int x)
{
    if(daddy[x] == 0) return x;
    else
    {
        int k = Root(daddy[x]);
        daddy[x] = k;
        return k;
    }
}

void Connect(int a, int b)
{
    int ra = Root(a);
    int rb = Root(b);

    if(ra != rb)
    {
        if(rang[ra] > rang[rb])
        {
            daddy[rb] = ra;
        }
        else
        {
            daddy[ra] = rb;
            if(rang[ra] == rang[rb])
                ++rang[ra];
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        fin >> muc[i].a >> muc[i].b >> muc[i].c;
    }

    sort(muc + 1, muc + m + 1, sortare);

    long long sum = 0;
    int cnt = 0;

    for(int i = 1; i <= m && cnt < n; ++i)
    {
        if(Root(muc[i].a) != Root(muc[i].b))
        {
            ++cnt;
            sum += muc[i].c;

            Connect(muc[i].a, muc[i].b);

            sol.push_back({muc[i].a, muc[i].b});
        }
    }

    fout << sum << "\n";
    fout << sol.size() << "\n";
    for(int i = 0; i < sol.size(); ++i)
    {
        fout << sol[i].first << " " << sol[i].second << "\n";
    }


    return 0;
}