#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int ma=400100;

int x[ma],y[ma],cost[ma],indice[ma],gr[ma],n,m;

vector<int>apm;

inline bool cmp(int i, int j)
{
    return cost[i]<cost[j];
}
int padure(int i)
{
    if(gr[i]==i) return i;

      gr[i]=padure(gr[i]);
      return gr[i];
}

void reun(int i, int j)
{
    gr[padure(i)]=padure(j);
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    int n,m;
    f>>n>>m;

    for(int i=1; i<=m; i++)
    f>>x[i]>>y[i]>>cost[i],indice[i]=i;

    for(int i=1; i<=n; i++)
    gr[i]=i;

    sort(indice+1, indice+m+1, cmp);

    int rez=0;
    for(int i=1; i<=m; i++)
    if(padure(x[indice[i]])!= padure(y[indice[i]]))
    {

        rez+=cost[indice[i]];
        reun(x[indice[i]], y[indice[i]]);
        apm.push_back(indice[i]);

    }
    g<<rez<<"\n"<<n-1<<"\n";


    for(int i=0; i<n-1; i++)
    g<<x[apm[i]]<<" "<<y[apm[i]]<<"\n";

    return 0;

}