#include <bits/stdc++.h>

using namespace std;

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

struct muchie{
    int x,y,cost;
};
int n,m;
vector<muchie>v;

void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        muchie aux;
        fin>>aux.x>>aux.y>>aux.cost;
        v.push_back(aux);
    }
}

vector <muchie> sol;

bool comp(const muchie &st, const muchie &dr)
{
    return st.cost<dr.cost;
}
vector<int>daddy;
int big_daddy(int node)
{
    int aux=node;
    int r;
    while(aux!=daddy[node])
    {
        aux=daddy[aux];
    }
    while(node!=daddy[node])
    {
        r=node;
        daddy[node]=aux;
        node=daddy[r];
    }
    return node;
}

void apm()
{
    daddy.resize(n+2);
    for(int i=1;i<=n;i++)
        daddy[i]=i;
    sort(v.begin(),v.end(),comp);
    for(auto edge:v)
    {
        if(sol.size()==n-1) return;
        int xbd=big_daddy(edge.x);
        int ybd=big_daddy(edge.y);
        if(xbd==ybd) continue;
        daddy[xbd]=ybd;
        sol.push_back(edge);
    }
}

void afis()
{

    int sum=0;
    for(auto edge:sol)
        sum+=edge.cost;
    fout<<sum<<endl;
    fout<<n-1<<endl;
    for(auto edge:sol)
    {
        fout<<edge.x<<" "<<edge.y<<endl;
    }
}

int main()
{
    citire();
    apm();
    afis();
    return 0;
}