#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;
    muchie aux;
    for(int i=1; i<=m; i++)
    {
        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[aux])
    {
         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 afisare()
{
    int sum=0;
    for(auto edge:sol)
        sum+=edge.cost;
    fout<<sum<<"\n"<<sol.size()<<"\n";
    for(auto edge:sol)
        fout<<edge.x<<" "<<edge.y<<endl;

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