#include <iostream>
#include <fstream>

#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");



/*
1. sortam muchiile desc dupa cost


solutie=0
M=[] - vectori de muchii  
parinte[i]=i pentru i=1..n
H[i]=1 pentru i=1..n   - inaltimea arborilor


2. for(x,y,c) apartin E
    daca find(x)!=find(y)
        sol+=c;
        M.push_back({x,y})
        Union(x,y)
print(sol)
print(M)


DSU:

Find(x)
    while(x!=parinte[x])
        x=parinte[x]
    return x

Union(x,y)
    x=Find(x);
    y=Find(y);

    if(x!=y)
    {
        if(H[x]<H[y])
            parintep[x]=y;
        else if(H[y]<H[x])
            parinte[y]=x;
        else --arborii au aceeasi inaltime
        {
            parinte[x]=y;
            H[y]++;
        }
    }

*/



struct muchie {
    int x,y,cost;
};

vector<muchie> graf; 
vector<int> parinte;
vector<int> H;

int sol=0;


int n,m;
void citire()
{
    fin>>n>>m;
    graf.reserve(m);
    for(int i=0;i<m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        graf.push_back({x,y,c});
    }
}
void initializare()
{
    parinte.resize(n+1);
    H.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        parinte[i]=i;
        H[i]=1;
    }
}
void sortare_muchii()
{
    //sortam crescator dupa cost
    sort(graf.begin(),graf.end(),[](muchie a,muchie b){
        return a.cost<b.cost;
    });
}

// DSU
int Find(int x)
{
    while(x!=parinte[x])
        x=parinte[x];
    return x;
}

int Union(int x,int y)
{
    x=Find(x);
    y=Find(y);

    if(x!=y)
    {
        if(H[x]<H[y])
            parinte[x]=y;
        else if(H[y]<H[x])
            parinte[y]=x;
        else // arborii au aceeasi inaltime
        {
            parinte[x]=y;
            H[y]++;
        }
        return 1;
    }
    return 0;
}

vector<pair<int,int>> M;

int main()
{
    citire();
    initializare();
    sortare_muchii();

    for(int i=0;i<m;i++)
    {
        int x=graf[i].x;
        int y=graf[i].y;
        int c=graf[i].cost;

        if(Union(x,y))
        {
            sol+=c;
            M.push_back({x,y});
        }
    }
    fout<<sol<<"\n";
    fout<<M.size()<<"\n";
    for(auto it:M)
        fout<<it.first<<" "<<it.second<<"\n";
    return 0;
}