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

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

int n, m;
int pre[NMAX], cmin[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()-1 << '\n';
    for(i = 1; i < afis.size(); i++)
        fout << afis[i].first << ' ' << afis[i].second << '\n';
    return 0;
}

void prim()
{
    int i, cost, vf, c, v;
    ///initializare
    for(i = 1; i <= n; i++)
        cmin[i] = INF;
    cmin[1] = 0;
    pq.push({0, 1});

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

        if(cost >= cmin[vf] && uz[vf])
            continue;
        cmin[vf] = cost;
        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] && c < cmin[v])
            {
                pq.push(i);
                pre[v] = vf;
            }
        }
    }
}