#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
struct Muchie{
    int u,v,w;
    Muchie(int u,int v,int w)
    {
        this->u=u;
        this->v=v;
        this->w=w;
    }
};
bool comparator(Muchie &m1,Muchie &m2)
{
    return m1.w<m2.w;
}
int n,m;
vector<Muchie> muchii;
vector<int> Reprez;
vector<pair<int,int>> Rezultat;
void Init()
{
    for(int i=1;i<=n;i++)
        Reprez[i] = i;
    for(int i=0;i<m;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        muchii.push_back(Muchie(x,y,w));
    }
    sort(muchii.begin(),muchii.end(),comparator);
}
void Reuneste(int u,int v)
{
    int r1 = Reprez[u];
    int r2 = Reprez[v];
    for(int i=1;i<=n;i++)
        if(Reprez[i] == r2)
            Reprez[i] = r1;
}
int main()
{
    cin>>n>>m;
    Reprez.resize(n+1);
    Init();
    int NrMuchii=0,GreutateTotala=0;
    for(int i=0;i<m;i++)
    {
        if(Reprez[muchii[i].u]!=Reprez[muchii[i].v])
        {
            GreutateTotala+=muchii[i].w;
            NrMuchii++;
            Rezultat.push_back(make_pair(muchii[i].u,muchii[i].v));
            Reuneste(muchii[i].u,muchii[i].v);
        }
        if(NrMuchii == n-1)
            break;
    }
    cout<<GreutateTotala<<'\n'<<n-1<<'\n';
    for(int i=0;i<n-1;i++)
        cout<<Rezultat[i].first<<' '<<Rezultat[i].second<<'\n';
    return 0;
}