#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

pair <int,pair<int,int> > g[400001],a[200001];
ifstream f("apm.in");
ofstream out("apm.out");

int T[101];
int H[101];
int n,m,i,k;

int root(int x)
{
    if (T[x]==0)
        return x;
    else
        return root(T[x]);
}

int main()
{
    f >> n >> m;
    for (i=1;i<=m;i++)
        f >> g[i].second.first >> g[i].second.second >> g[i].first;
    sort(g+1,g+m+1);
    k=0;
    for (i=1;i<=m;i++)
    {
        int v1 = g[i].second.first;
        int v2 = g[i].second.second;
        int r1 = root(v1);
        int r2 = root(v2);
        //cout << v1 << v2 << endl;
        if ( r1 != r2)
        {
            k++;
            a[k] = g[i];
            if (H[r1] > H[r2])
                T[r2] = r1;
            else
                if (H[r1]<H[r2])
                    T[r1] = r2;
                else
                    {
                        T[r2] = r1;
                        H[r1]++;
                    }

            if (k==n-1)
                break;
        }
    }
    int c=0;
    for (i=1;i<=n-1;i++)
        c+=a[i].first;
    out << c << "\n";
    out << n-1 << "\n";
    for (i=1;i<=n-1;i++)
        out << a[i].second.first<<' '<<a[i].second.second<<endl;
    return 0;
}