#include <bits/stdc++.h>
#define Maxx 200002
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

struct muchie{int x,y,c;}x;
vector<muchie> m;
vector<pair <int,int> > lista;
bool compareMuchie(muchie a,muchie b)
{
    return (a.c<b.c);
}
int n,k,tata[Maxx],s;

/**int tataa(int x)
{
    if(tata[x]!=x)
        return tataa(tata[x]);
    return x;
}*/
int main()
{
    in>>n>>k;
    for(int i=1;i<=n;i++)
        tata[i]=i;
    for(int i=1;i<=k;i++)
    {
        in>>x.x>>x.y>>x.c;
        m.push_back(x);
    }
    sort(m.begin(),m.end(),compareMuchie);
    for(auto a:m)
    {
        if(tata[a.x]!=tata[a.y])
        {
            s+=a.c;
            lista.push_back({a.x,a.y});
            if(tata[a.x]==a.x)
                tata[a.x]=tata[a.y];
            else if(tata[a.y]==a.y)
                tata[a.y]=tata[a.x];
            else
            {
                for(int i=1;i<=n;i++)
                    if(tata[i]==tata[a.x] && i!=a.x) tata[i]=tata[a.y];
                tata[a.x]=tata[a.y];
            }
        }
    }
    /**for(auto a:m)
    {
        if(tataa(a.x)!=tataa(a.y))
        {
            s+=a.c;
            if(tata[a.x]==a.x && tata[a.y]==a.y)
            {
                if(a.x<a.y)
                    tata[a.y]=a.x;
                else
                    tata[a.x]=a.y;
            }
            else if(tata[a.x]==a.x)
                tata[a.x]=a.y;
            else if(tata[a.y]==a.y)
                tata[a.y]=a.x;
            else
                tata[tataa(a.x)]=a.y;
            lista.push_back({a.x,a.y});
        }
    }*/
    out<<s<<'\n'<<lista.size()<<'\n';
    for(auto a:lista)
        out<<a.first<<' '<<a.second<<'\n';
    return 0;
}