#include <fstream>
#include <vector>
#include <algorithm>
#define mp make_pair
#define pb push_back
#define f first
#define s second

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n,m,t[400000],cost=0;
bool sel[400000];
vector <pair<int, int> > sol;
vector <pair <int, pair<int, int> > > l;
int rad(int nod)
{
    if(t[nod]!=nod)
        t[nod]=rad(t[nod]);
    return t[nod];
}

void leaga(int i,int j)
{
    int k;
    i=t[i];
    j=t[j];
    if(i==j)
        return;
    for(k=1;k<=n;k++)
        if(t[k]==i)
            t[k]=j;
}

void kruskal()
{
    int i,j,k,c,n1,n2;
    for(i=0;i<=n;i++)
        t[i]=i,sel[i]=false;
    for(i=0;i<=m;i++)
    {
        n1=l[i].s.f;
        n2=l[i].s.s;
        if(rad(n1)!=rad(n2))
        {
            cost+=l[i].f;
            sol.pb(mp(n1,n2));
            t[t[n2]]=t[n1];
        }
    }
    fout<<cost<<"\n"<<sol.size()<<"\n";

}
int main()
{
    int  x,y,c,i;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>x>>y>>c;
        l.pb(mp(c,mp(x,y)));
    }
    sort(l.begin(),l.end());
    kruskal();
    for(i=0;i<=sol.size();i++)
        if(sel[i])
            fout<<sol[i].f<<" "<<sol[i].s<<"\n";

    return 0;
}