#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#define Inf 2000000000
#define nmax 200005
using namespace std;

int costTotal, n, m, nrMuchiiArbore;
vector< vector<int> > A;
vector<int> aux, Tata;
vector<bool> apartineArbore;
vector< pair<int,int> >Sol;

void citire()
{
    int x,y,c;
    cin>>n>>m;
    aux.assign(n+2, Inf);
    Tata.assign(n+2, 0);
    apartineArbore.assign(n+2, 0);
    for(int i=0; i<=n; i++)
        A.push_back(aux);

    for(int i=1;i<=m;i++){
        scanf("%d %d %d", &x, &y, &c);
        A[x][y]=A[y][x]=c;
    }
}

void Prim(int radacina)
{
    int cmin,a,b;
    apartineArbore[radacina]=1;//se alege radacina arborelui ca fiind 1
    for(int i=1;i<n;i++)
    {
        cmin=Inf;
        //se cauta o muchie minima de la un x din arbore la un y ce nu apartine arborelui
        for(int x=1; x<=n; x++)
            if(apartineArbore[x])
                for(int y=1; y<=n; y++)
                    if(!apartineArbore[y])
                        if(cmin > A[x][y]){
                            cmin = A[x][y];
                            a=x;    b=y;
                        }
        //Tata[b]=a;//construire vector de tati

        if(cmin != Inf)
        apartineArbore[b]=1;
        costTotal+=cmin;
        Sol.push_back(make_pair(a,b));  //salvam muchia pentru afisare
        nrMuchiiArbore++;
    }
}

int main()
{
    freopen("apm.in","rt",stdin);
    freopen("apm.out","wt",stdout);
    citire();
    Prim(1);
    cout<<costTotal<<'\n'<<n-1<<'\n';
    for(int i=0 ; i<n-1; i++)
        cout<<Sol[i].first<<' '<<Sol[i].second<<'\n';


    return 0;
}