#include <fstream>
#include <iostream>
using namespace std;
struct Muchie
{
    int e1,e2,cost;
};
Muchie G[400000];
int A[200000],c[200000];
int n,m;
void SortareMuchii(int st, int dr)
{
    int i,j;
    Muchie x;
        if(st<dr)
        {
        x=G[st]; i=st;j=dr;
        while(i<j)
        {
            while(i<j && G[j].cost>=x.cost)
                j--;
            G[i]=G[j];
            while(i<j && G[i].cost<=x.cost)
                i++;
            G[j]=G[i];
        }
        G[i]=x;
        SortareMuchii(st,i-1);
        SortareMuchii(i+1,dr);
        }
}
int main()
{
    int i,j,mini,maxi,nr,costapm=0;
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>G[i].e1>>G[i].e2>>G[i].cost;
    for(i=1;i<=n;i++)
        c[i]=i;
    SortareMuchii(1,m);
    nr=0;
    for(i=1;nr<n-1;i++)
        if(c[G[i].e1]!=c[G[i].e2])
           {
                A[++nr]=i;
                if(c[G[i].e1]<c[G[i].e2])
                {
                    mini=c[G[i].e1];
                    maxi=c[G[i].e2];
                }
                else
                {
                    mini=c[G[i].e2];
                    maxi=c[G[i].e1];
                }
                for(j=1;j<=n;j++)
                    if(c[j]==maxi)
                        c[j]=mini;

           }
           for(i=1;i<n;i++)
                costapm+=G[A[i]].cost;
            fout<<costapm<<"\n"<<n-1<<"\n";
            for(i=1;i<n;i++)
                fout<<G[A[i]].e2<<" "<<G[A[i]].e1<<"\n";
fin.close();
}