#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
int n, m, cost, vf[400001], k=1, root[200001];
struct strct {int first; int second; int cost;}v[400001];

bool cmp(strct a, strct b)
{
    if(a.cost<b.cost) return true;
    return false;
}

int findRoot (int x)
{
    if(x==root[x])
    {
        return root[x];
    }
    else
        return root[x]=findRoot(root[x]);
}
void unite (int x, int y)
{
    if(x!=y)
    {
        root[y]=x;
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        root[i]=i;
    }
    for(int i=1; i<=m; i++)
    {
        fin>>v[i].first>>v[i].second>>v[i].cost;
    }
    sort(v + 1, v + m + 1, cmp);
    for(int i=1; i<=m; i++)
    {
        if(findRoot(v[i].first)==findRoot(v[i].second))
            continue;
        unite(findRoot(v[i].first), findRoot(v[i].second));
        cost=cost+v[i].cost;
        vf[k++]=i;
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1; i<=k-1; i++)
    {
        fout<<v[vf[i]].first<<' '<<v[vf[i]].second<<'\n';
    }
    return 0;
}