/// https://www.infoarena.ro/job_detail/3364849
/// rezolvare de 100p
/// Algoritmul lui Kruskal
/// utilizare paduri de multimi disjuncte

#include <bits/stdc++.h>

using namespace std;
int N,M;
int tata[200005], sizes[200005];
struct graf
{
    int nod1,nod2,cost;
};
graf muchii[400005];

bool cmp(graf a, graf b)
{
    return a.cost < b.cost;
}

void initPaduri()
{
    for(int i = 1; i<=N; i++)
    {
        tata[i] = i;
        sizes[i] = 1;
    }
}

int getTata(int nod)
{
    if(tata[nod] != nod)
    {
        tata[nod] = getTata(tata[nod]);
    }
    return tata[nod];
}

int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    long long sum = 0;
    vector<pair<int,int>> sol;

    cin>>N>>M;
    for(int i=1; i<=M; i++)
    {
        cin>>muchii[i].nod1>>muchii[i].nod2>>muchii[i].cost;
    }

    sort(muchii + 1, muchii + M + 1,cmp);

    initPaduri();
    for(int i = 1; i <= M; i++)
    {
        ///verificam daca putem pune muchia (trebuie sa nu se formeze un ciclu)
        /// verificam prin paduri de multimi disjuncte
        getTata(muchii[i].nod1);
        getTata(muchii[i].nod2);
        if(tata[muchii[i].nod1] != tata[muchii[i].nod2])
        {
            /// se poate pune muchia
            sum += muchii[i].cost;

            /// punem multimea mai mica in multimes mai mare
            if(sizes[tata[muchii[i].nod2]] < sizes[tata[muchii[i].nod1]])
            {
                sizes[tata[muchii[i].nod1]] += sizes[tata[muchii[i].nod2]];
                tata[tata[muchii[i].nod2]] = tata[muchii[i].nod1];
            }
            else
            {

                sizes[tata[muchii[i].nod2]] += sizes[tata[muchii[i].nod1]];
                tata[tata[muchii[i].nod1]] = tata[muchii[i].nod2];
            }
            sol.push_back({muchii[i].nod1, muchii[i].nod2});
        }
    }
    cout<<sum<<'\n';
    cout<<sol.size()<<'\n';
    for(auto it:sol)
    {
        cout<<it.first<<' '<<it.second<<'\n';
    }
    return 0;
}