#include <bits/stdc++.h>
#define N 31202
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
int cc[N],fol[N];
struct mch { int x,y,d; } v[N];
list <int> el[N];
bool cmp(mch a,mch b)
{
    return a.d<b.d;
}
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].d;
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++)
        cc[i]=i;///fiecare varf este o comp conexa
    for(int i=1;i<=n;i++)
        el[i].push_back(i);///feicare cc are doar un elem
    int p=0,s=0,cc1,cc2;
    while(p<m)
    {
        p++;///incercam sa adaugam muchiia p
        if(cc[v[p].x]==cc[v[p].y])
            continue ;///cele 2 elem se afla in aceasi lista
        fol[p]=1;
        s+=v[p].d;
        ///alegem lista el[cc[v[p].x]] sau el[cc[v[p].y]] cu elem mai putine
        if(el[cc[v[p].x]].size()< el[cc[v[p].y]].size())///prima lista va avea mai multe elem
            swap(v[p].x,v[p].y);///a 2-a lista va avea mai putine elem
        fol[p]=2;
        ///elem din a 2-a cc le trecem in prima
        cc1=cc[v[p].x];
        cc2=cc[v[p].y];
        for(list <int>::iterator it=el[cc2].begin();it!=el[cc2].end();it++)///parcurgem lista el[cc[v[p].y]]
            cc[*it]=cc1;
        ///elem din a 2-a lista le trecem in prima lista
        el[cc1].insert(el[cc1].begin(),el[cc2].begin(),el[cc2].end());
    }
    g<<s<<"\n"<<n-1<<"\n";

    for(int i=1;i<=m;i++)
        if(fol[i]==1)
            g<<v[p].x<<" "<<v[p].y<<"\n";
        else if ( fol[i]==2)  g<<v[p].y<<" "<<v[p].x<<"\n";
}