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

struct muchie
{
    int a,b,cost;
}v[400005];

int t[200005];
bool sortfunc(muchie x,muchie y)
{
    return (x.cost < y.cost);
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n,m;
    vector<muchie> vres;
    cin >> n >> m;
    for(int i=0;i<m;i++)
        cin >> v[i].a >> v[i].b >> v[i].cost;
    sort(v, v+m, sortfunc);
    for(int i=1;i<=n;i++)
        t[i] = i;
    int res = 0;
    for(int i=0;i<m;i++)
    {
        int ta=t[v[i].a];
        int tb=t[v[i].b];
        if(ta != tb)
        {
            vres.push_back(v[i]);
            res += v[i].cost;
            for(int j=1;j<=n;j++)
            {
                if(t[j] == tb)
                    t[j] = ta;
            }
        }
    }
    cout << res << '\n';
    cout << n-1 << '\n';
    for(auto x : vres)
    {
        cout << x.a << " " << x.b << '\n';
    }
    return 0;
}