#include <bits/stdc++.h>
#define NMAX 200002

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

int n, m;
int pre[NMAX];
bool uz[NMAX];
long long apm;

///first e costul (ptr greater), second e vf asociat
priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector <pair<int, int>> muchii[NMAX];
vector <pair<int, int>> afis;

void prim();

int main()
{
    int i, x, y, cost;

    ///citire
    fin >> n >> m;
    while(fin >> x >> y >> cost)
    {
        muchii[x].push_back({cost, y});
        muchii[y].push_back({cost, x});
    }

    prim();

    ///afisare
    fout << apm << '\n';
    fout << afis.size() << '\n';
    for(auto i : afis)
        fout << i.first << ' ' << i.second << '\n';
    return 0;
}

void prim()
{
    int i, cost, vf, c, v;
    ///initializare
    for(auto i : muchii[1])
    {
        pq.push(i);
        pre[i.second] = 1;
    }
    uz[1] = true;


    while(!pq.empty())
    {
        cost = pq.top().first;
        vf = pq.top().second;
        pq.pop();

        if(uz[vf])
            continue;
        uz[vf] = true;
        apm += cost;
        afis.push_back({vf, pre[vf]});

        for(auto i : muchii[vf])
        {
            c = i.first;
            v = i.second;
            if(!uz[v])
            {
                pq.push(i);
                pre[v] = vf;
            }
        }
    }
}