#include<iostream>
#include<fstream>
 
using namespace std;

typedef struct m{
	int x,y,c;
} muchie;

muchie M[400001],vec[400001];
int indice[200001], c[100001];
void merge (int a, int q, int b)
    {
        int i=0,p1,p2;
        p1=a; p2=q+1;
         
        while (p1<=q || p2<=b)
            if (p1<=q && p2<=b)
                if (M[p1].c<M[p2].c)
                    vec[++i]=M[p1++];
                else
                    vec[++i]=M[p2++];
            else if (p1<=q)
                vec[++i]=M[p1++];
            else
                vec[++i]=M[p2++];
         
        for (i=a; i<=b; i++)
            M[i]=vec[i-a+1];
    }
 
 
void sort (int a, int b)
    {   int q;
        if (a<b)
            {
                q=(a+b)/2;
                sort (a,q);
                sort (q+1,b);
                merge (a,q,b);
            }
    }
 
int main()
{
    int n,i,m,nrm=0,j,x,y,cost=0,pas=0,nrc=0,cap1[100001],cap2[100001];
    ifstream f("apm.in");
    ofstream g("apm.out");
     
    f>>n>>m;
    for (i=1; i<=m; i++)
		f>>M[i].x>>M[i].y>>M[i].c;

    sort (1,m);
	
	while (nrm<n-1){
		int ok=0;
		pas++;
		x=M[pas].x;
		y=M[pas].y;
		if (c[indice[x]]==0 && c[indice[y]]==0){
			nrc++;
			c[nrc]=nrc;
			indice[x]=indice[y]=nrc;
			ok=1;
		}
		else if (c[indice[x]]==0 && c[indice[y]]!=0){
			indice[x]=indice[y];
			ok=1;
		}
		else if (c[indice[x]]!=0 && c[indice[y]]==0){
			indice[y]=indice[x];
			ok=1;
		}
		else if (c[indice[x]]!=c[indice[y]]){
			for (j=1; j<=nrc; j++)
				if (c[j]==c[indice[y]] && j!=indice[y]) c[j]=c[indice[x]];
			c[indice[y]]=c[indice[x]];
			ok=1;
		}
		if (ok){  //muchia a fost adaugata
			nrm++;
			cap1[nrm]=x;
			cap2[nrm]=y;
			cost+=M[pas].c;
		}
	}
	cout<<pas;
	g<<cost<<"\n"<<nrm<<"\n";
	for (i=1; i<=nrm; i++)
		g<<cap1[i]<<" "<<cap2[i]<<"\n";

    return 0;
}