#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
using namespace std;

//ifstream fin("apm.in");
FILE * fin = fopen("apm.in","rt");
ofstream fout("apm.out");

pair < int, pair<int,int> > v[400001],w[200001];

int n,m,c[100],S;
int T[200001];
int H[200001];
int root(int x)
{
    if (T[x]==0)
        return x;
    else
        return root(T[x]);
}

int main() {
    //fin >> n >> m;
    fscanf(fin,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        //fin >> v[i].second.first >> v[i].second.second >> v[i].first;
        fscanf(fin,"%d%d%d",&(v[i].second.first),&(v[i].second.second), &(v[i].first));
    sort(v+1,v+m+1);

    int ct=1;
    for(int i=1;i<=m;i++) {
        int v1,v2;
        v1=v[i].second.first; v2=v[i].second.second;
        int r1 = root(v1);
        int r2 = root(v2);
        //cout << v1 << '-' <<root(v1) << "  " <<v2 <<'-'<< root(v2)<<endl;
        if(r1!=r2)
        {
           if (H[r1]==H[r2])
           {
               T[r1]=r2;
               H[r2]++;
           }
           else
            if (H[r1]>H[r2])
                T[r2]=r1;
            else
                T[r1]=r2;

          w[ct]=v[i];
          ct++;
          S+=v[i].first;
          if(ct==n) break;
        }
    }
    fout << S << endl << n-1 << endl;
    for(int i=1;i<=n-1;i++)
        fout << w[i].second.first << ' ' << w[i].second.second << '\n';
    return 0;
}

/*#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("apm.in");

pair < int, pair<int,int> > v[10000],w[100];

int n,m,c[100],S;

int main() {
    fin >> n >> m;
    for(int i=1;i<=m;i++)
        fin >> v[i].second.first >> v[i].second.second >> v[i].first;
    sort(v+1,v+m+1);

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

    int ct=1;
    for(int i=1;i<=m;i++) {
        int v1,v2;
        v1=v[i].second.first; v2=v[i].second.second;
        if(c[v1]!=c[v2]) {
            w[ct]=v[i];
            ct++;
            S+=v[i].first;
            if(ct==n) break;

            int mem=c[v1];
            replace(c+1,c+n+1,mem,c[v2]);

        }
    }
    cout << S << endl;
    for(int i=1;i<=n-1;i++)
        cout << w[i].second.first << ' ' << w[i].second.second << endl;
    return 0;
}*/