#include <iostream>
#include <bits/stdc++.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
int par[100005];   // vector pentru parinti
int dim[100005];  //cat de multe noduri sunt in arborele respectiv
vector<pair<int,pair<int,int>>> muchii; // m.first -> costul muchiei, m.second.first -> nodul from, m.second.second -> nodul to
vector<pair<int,int>> muchii_folosite;
int find_radacina(int x)
{
    vector <int> met;
    while(x!=par[x])  //parcurgem cat timp x are parinte
    {
        x=par[x];
        met.push_back(x);
    }
    for(auto el:met)
    {
        par[el] = x;
    }
    return x;
}

void unite(int a, int b)
{
    int x = find_radacina(a);
    int y = find_radacina(b);
    if(dim[x] > dim[y])         //unim arborele mai mic de arborele mai mare
    {
        par[y] = x;
        dim[x]+=dim[y];
    }
    else
    {
        par[x] = y;
        dim[y] += dim[x];
    }

}

int main()
{
    int n, m;

    fin>> n >> m;
    while(m--)
    {
        pair<int,pair<int,int>> mc; //muchie curenta
        fin>>mc.second.first>>mc.second.second>>mc.first; //muchia curenta a fost citita
        muchii.push_back(mc);      //pune muchia curenta in vectorul mare
    }
    sort(muchii.begin(), muchii.end());
    for(int i=1; i<=n; i++)
    {
        par[i] = i;
    }

    int costTotal = 0;
    for(int m = 0; m < muchii.size(); m++)
    {
        if(find_radacina(muchii[m].second.first) != find_radacina(muchii[m].second.second))  //daca parintii celor doua noduri sunt diferiti
        {

            costTotal +=  muchii[m].first;
            unite(muchii[m].second.first, muchii[m].second.second);    //uneste nodurile

            pair<int,int> p;
            p.first = muchii[m].second.first;
            p.second = muchii[m].second.second;       //pune muchiile folosite in vector
            muchii_folosite.push_back(p);
        }
    }

    fout << costTotal<<'\n';
    fout<<muchii_folosite.size()<<'\n';
    for(int i=0; i<muchii_folosite.size();i++)
    {

        fout<<muchii_folosite[i].first<<" "<<muchii_folosite[i].second<<'\n';
    }

    return 0;
}