#include <bits/stdc++.h>
using namespace std;
int n, m, i, x, y;
bool seen[200005];
struct pereche
{
    int cost, varf, tata;
};
struct verticle
{
    int st, dr;
};
vector <verticle> muchii_apm;
struct cmp
{
    bool operator() (pereche a, pereche b)
    {
        return a.cost > b.cost;
    }
};
vector <pereche> v[200005];
int cost_total, c, dad[200005];
priority_queue <pereche, vector<pereche>, cmp> Heap;
void Prim(int start)
{
    pereche aux;
    aux.varf = 1;
    aux.cost = 0;
    aux.tata = 0;
    Heap.push(aux);
    for(int i = 0; i < n; i ++)
    {
        while(!Heap.empty())
        {
            pereche aux1 = Heap.top();
            if(seen[aux1.varf] == false)break;
            Heap.pop();
        }
        if(Heap.empty())break;
        pereche muchie = Heap.top();
        if(muchie.tata != 0)
        {
            verticle muc;
            muc.st = muchie.tata;
            muc.dr = muchie.varf;
            muchii_apm.push_back(muc);
        }
        dad[muchie.varf] = muchie.tata;
        if(seen[muchie.varf] == true)
        {
            i --;
            continue;
        }
        Heap.pop();
        //cout << muchie.varf << "\n";
        seen[muchie.varf] = true;
        cost_total += muchie.cost;
        for(int j = 0; j < v[muchie.varf].size(); j ++)
            if(seen[v[muchie.varf][j].varf] == false)
            {
                pereche aux1;
                aux1.varf = v[muchie.varf][j].varf;
                aux1.cost = v[muchie.varf][j].cost;
                aux1.tata = muchie.varf;
                Heap.push(aux1);
            }
    }
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for(i = 1; i <= m; i ++)
    {
        f >> x >> y >> c;
        pereche aux;
        aux.cost = c;
        aux.varf = y;
        v[x].push_back(aux);
        aux.cost = c;
        aux.varf = x;
        v[y].push_back(aux);
    }
    Prim(1);
    g << cost_total << "\n";
    g << muchii_apm.size() << "\n";
    for(i = 0; i < muchii_apm.size(); i ++)
        g << muchii_apm[i].st << " " << muchii_apm[i].dr << "\n";
    return 0;
}