#include <bits/stdc++.h>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct muchie{
    int x,y,c;
};
vector<int>daddy;
vector<muchie>sol;
vector<muchie>v;
bool comp(const muchie &st,const muchie &dr)
{
    return st.c<dr.c;
}
void citire()
{
    f>>n>>m;
    muchie aux;
    for(int i=1;i<=m;i++)
    {

        f>>aux.x>>aux.y>>aux.c;
        v.push_back(aux);
    }
}
int big_daddy(int node)
{
    int aux=node;
    while(aux!=daddy[aux]){
        aux=daddy[aux];
    }
    daddy[node]=aux;
    node=daddy[node];
    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);
    }
}
int sm;
void afis()
{
    for(auto el:sol)
        sm+=el.c;
    g<<sm<<"\n";
    g<<sol.size()<<"\n";
    for(auto el:sol)
        g<<el.x<<" "<<el.y<<"\n";
}
int main()
{
    citire();
    apm();
    afis();
    return 0;
}