#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
vector <pair<int,int> >G[200005];
vector <pair<int,pair<int,int> > >M;
vector <int> sol;
int vTati[200005],vRad[200005];
int n,m;
void citire()
{
    int nod1,nod2,costm;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&nod1,&nod2,&costm);
        G[nod1].push_back({nod2,costm});
        G[nod2].push_back({nod1,costm});
        M.push_back({costm,{nod1,nod2}});
    }
    sort(M.begin(),M.end());
}
int getRad(int nod)
{
    int aux=nod;
    while(aux!=vRad[aux])
    {
        aux=vRad[aux];
    }
    vRad[nod]=aux;
    return vRad[nod];
}
int kruskal()
{
    int costapm=0,id=0;
    for(auto muchie:M)
    {
        if(getRad(muchie.second.first)!=getRad(muchie.second.second))
        {
            costapm+=muchie.first;
            sol.push_back(id);
            vRad[getRad(muchie.second.first)]=getRad(muchie.second.second);
        }
        id++;
    }
    return costapm;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
    {
        vTati[i]=i;
        vRad[i]=i;
    }
    printf("%d\n%d\n",kruskal(),n-1);
    for(auto it:sol)
        printf("%d %d\n",M[it].second.first,M[it].second.second);
    return 0;
}