#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

#define maxn 400100
#define pb push_back
ifstream in("apm.in");
ofstream out("apm.out");

struct arc
{

    int a,b;
    int cost;

}graf[maxn];

int n,m;
int root[maxn];
int best;

bool comp(const arc &a,const arc &b)
{
    return a.cost <= b.cost;
}

vector<int> sol;
vector<int> :: iterator it;


int grup(int nod)
{
    int cr = nod,aux;
    for(nod = root[nod];root[nod] != nod;nod = root[nod]);
    for(;cr != nod;)
    {
        aux = root[cr];
        root[cr] = nod;
        cr = aux;
    }
    return nod;
}

void unite(int a,int b)
{
    a = grup(a);
    b = grup(b);
    root[a] = b;
}

int main()
{
    int i,j;
    int x,y,c;
    in >> n >> m;
    for(i=1;i<=m;++i)
        in >> graf[i].a >> graf[i].b >> graf[i].cost;

    sort(graf+1,graf+m+1,comp);

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

    for(i=1;i<=m;++i)
    {
        if(grup(graf[i].a) != grup(graf[i].b))
        {
            best += graf[i].cost;
            unite(graf[i].a,graf[i].b);
            sol.pb(i);
        }
    }
    out << best << "\n";
    out << sol.size() << "\n";
    for(it=sol.begin();it!=sol.end();++it)
        out << graf[*it].a << " " << graf[*it].b << "\n";
    return 0;
}