#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
bitset <400001> viz;
int n, m, tata[200001], cost=0;
int find_tata(int x)
{
    if(tata[x]==x)
        return x;
    int t=find_tata(tata[x]);
    tata[x]=t;
    return t;
}
struct graf
{
    int u, v, w;

}v[400001];
bool cmp(graf a,graf b)
{
    return a.w<b.w;
}
int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
        fin>>v[i].u>>v[i].v>>v[i].w;
    sort(v+1, v+1+m, cmp);
    for(int i=1; i<=n; ++i)
        tata[i]=i;
    for(int i=1; i<=m; ++i)
    {
        int tx=find_tata(v[i].u), ty=find_tata(v[i].v);
        if(tx != ty)
        {
            viz[i]=1;
            tata[tx]=ty;
            cost=cost+v[i].w;
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1; i<=m; ++i)
        if(viz[i]==1)
            fout<<v[i].u<<' '<<v[i].v<<'\n';
    return 0;
}