#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie {
    int x,y,cost;
};
vector<muchie>v;
int n,m,sm,k;
vector<muchie>sol;
void citire()
{
    f>>n>>m;
    muchie aux;
    for(int i=1;i<=m;i++)
    {
        f>>aux.x>>aux.y>>aux.cost;
        v.push_back(aux);
    }
}
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[aux])
    {
        aux=daddy[aux];
    }
    while(node!=daddy[node])
    {
        r=daddy[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 afisare()
{
    for(auto edge:sol)
        sm+=edge.cost;
    g<<sm<<"\n";
    for(auto edge:sol)
        k++;
    g<<k<<"\n";
    for(auto edge:sol)
        g<<edge.x<<" "<<edge.y<<endl;

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