#include <bits/stdc++.h>
#define NMAX 200005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m;
struct edge
{
    int x, y, cost;
};
edge v[NMAX];
int viz[NMAX];
int t[NMAX];
long long s;
int counter;

int tata(int nod)
{
    if(t[nod]==nod)
        return nod;
    t[nod]=tata(t[nod]);
    return t[nod];
}
bool comp(edge a, edge b)
{
    return a.cost<b.cost;
}
void read();
int main()
{
    read();
    sort(v+1, v+m+1, comp);
    for(int i=1; i<=n; ++i)
        t[i]=i;

    for(int i=1; i<=m; ++i)
    {
        if(tata(v[i].x)==tata(v[i].y))
            continue;
        viz[i]=1;
        s+=v[i].cost;
        int ax=t[v[i].x];
        int ay=t[v[i].y];

        t[tata(ay)]=tata(ax);
    }

    fout<<s<<'\n';
    fout<<n-1<<'\n';
    for(int i=1; i<=m; ++i)
    {
        if(viz[i])
        {
            fout<<v[i].x<<' '<<v[i].y<<'\n';
        }
    }
    return 0;
}
void read()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        fin>>v[i].x>>v[i].y>>v[i].cost;
    }
}