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


ifstream in("apm.in");
ofstream out("apm.out");


int n,m;
struct muchie
{
    int a,b,c;
} muchii[400000];


bool compare(muchie a,muchie b)
{
    return a.c<b.c;
}

int comp_conex[200001];

void read()
{
    in>>n>>m;
    for(int i=0; i<m; i++)
    {
        in>>muchii[i].a>>muchii[i].b>>muchii[i].c;
    }

    for(int i=1; i<=n; i++)
        comp_conex[i]=i;
}

void solve()
{
    int cost=0;
    int componente_conexe=n;
    sort(muchii,muchii+m,compare);
    vector<std::pair<int,int>> results;
    int k=0;

    while(componente_conexe>1)
    {
        if(comp_conex[muchii[k].a]!=comp_conex[muchii[k].b])
        {
            int p=comp_conex[muchii[k].b];
            int q=comp_conex[muchii[k].a];
            for(int i=1; i<=n; i++)
            {
                if(comp_conex[i]==p)
                    comp_conex[i]=q;
            }
            results.push_back({muchii[k].a,muchii[k].b});

            cost+=muchii[k].c;
            componente_conexe--;
        }
        k++;
    }
    out<<cost<<'\n'<<results.size()<<'\n';
    for(auto result:results)
        out<<result.first<<" "<<result.second<<'\n';

}


int main()
{
    read();
    solve();
    return 0;
}