#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int NMAX=200005;
int n,muchii,t[NMAX];
struct T
{
    int nod,nod1,cost;
    bool ok;
};
T a[NMAX];
inline void UNION(int x,int y)
{
    t[y]=x;
}
inline int Find(int x)
{
    int rad,y;
    rad=x;
    while(t[rad])
        rad=t[rad];
    while(x!=rad)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return x;
}
inline bool SORT(const T A,const T B)
{
    return A.cost<B.cost;
}
inline void READ()
{
    fin>>n>>muchii;
    for(int i=1;i<=muchii;i++)
        fin>>a[i].nod>>a[i].nod1>>a[i].cost;
}
inline void SOLVE()
{
    long long solcost=0;
    sort(a+1,a+muchii+1,SORT);
    for(int i=1;i<=muchii;i++)
    {
        int x,y;
        x=a[i].nod;
        y=a[i].nod1;
        x=Find(x);
        y=Find(y);
        if(x!=y)
        {
            UNION(x,y);
            solcost+=a[i].cost;
            a[i].ok=true;
        }
    }
    fout<<solcost<<"\n"<<(n-1)<<"\n";
    for(int i=1;i<=muchii;i++)
        if(a[i].ok)
            fout<<a[i].nod<<" "<<a[i].nod1<<"\n";
}
int main()
{
    READ();
    SOLVE();
    fin.close();
    fout.close();
    return 0;
}