#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
struct muchie
{
    int x;
    int y;
    int c;
};
vector <muchie> M;
vector < pair <int, int> > V;
int t[200005],n,m,i,x1,y2,c1,cost,nod1,nod2;
bool cmp(muchie a, muchie b)
{
    if (a.c>b.c) return false;
    return true;
}
void reuneste(int a, int b)
{
    int a1=a,b1=b;
    while (t[a1]!=a1) a1=t[a1];
    while (t[b1]!=b1) b1=t[b1];
    t[b1]=a1;
}
bool multime(int a, int b)
{
    int a1=a,b1=b;
    while (t[a1]!=a1) a1=t[a1];
    while (t[b1]!=b1) b1=t[b1];
    if (a1==b1) return 1;
    return 0;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d",&x1,&y2,&c1);
        muchie muchie1;
        muchie1.x=x1;
        muchie1.y=y2;
        muchie1.c=c1;
        M.push_back(muchie1);
    }
    sort(M.begin(),M.end(),cmp);
    for (i=1; i<=n; i++) t[i]=i;
    cost=0;
    for (i=0; i<m; i++)
    {
        nod1=M[i].x;
        nod2=M[i].y;
        if (!multime(nod1, nod2))
        {
            cost+=M[i].c;
            V.push_back(make_pair(nod1,nod2));
            reuneste(nod1,nod2);
        }
    }
    printf("%d\n",cost);
    printf("%d\n",V.size());
    for (i=0; i<V.size(); i++) printf("%d %d\n",V[i].first, V[i].second);
    return 0;
}