#include <fstream>
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, i, j, x1, y, dist[200005], c, sum, nr, parent[200005], sze[200005];
bool viz[200005];
struct nod
{
    int x, y, cost;
}ans[200005];
int find_set(int nod)
{
    if(nod==parent[nod])
        return nod;
    return parent[nod]=find_set(parent[nod]);
}
void union_set(int a, int b)
{
    a=find_set(a);
    b=find_set(b);
    if(a!=b)
    {
        if(sze[a]>sze[b])
            swap(a, b);
        parent[b]=a;
        sze[a]+=sze[b];
    }
}
bool cmp(nod a, nod b)
{
    return a.cost<b.cost;
}
vector <nod> v;
int main()
{
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x1>>y>>c;
        v.push_back({x1, y, c});
    }
    for(i=1; i<=n; i++)
        parent[i]=i;
    sort(v.begin(), v.end(), cmp);
    for(auto i: v)
    {
        if(find_set(i.x)!=find_set(i.y))
        {
            ans[++nr]={i.x, i.y, 0};
            sum+=i.cost;
            union_set(i.x, i.y);
        }
    }
    fout<<sum<<'\n';
    fout<<nr<<'\n';
    for(i=1; i<=nr; i++)
        fout<<ans[i].x<<" "<<ans[i].y<<'\n';
    return 0;
}