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

ifstream fin("apm.in");
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;
    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(root(v1)!=root(v2))
        {
           if (H[v1]==H[v2])
           {
               T[v1]=v2;
               H[v2]++;
           }
           else
            if (H[v1]>H[v2])
                T[v2]=v1;
            else
                T[v1]=v2;

          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 << endl;
    return 0;
}