#include <fstream>'
#include<algorithm>
#include<vector>

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int GR[400100],n,rez,IND[400100],m;
vector<int> VANS;
struct mu{
    int x,y,c;}muchie[400100];
bool cmp (int i,int j)
{
    return(muchie[i].c<muchie[j].c);
}

int grupa(int i)
{
    if (GR[i]==i) return i;
    GR[i]=grupa(GR[i]);
    return GR[i];
}
void add(int i,int j)
{
    GR[grupa(i)]=grupa(j);
}
int main()
{f>>n>>m;
for(int i = 1;i<=m;++i)
    {
       f>>muchie[i].x>>muchie[i].y>>muchie[i].c;
        IND[i] = i;
    }
     for(int i = 1;i <=n; ++i)
            GR[i] = i;
    sort(IND+1,IND+m+ 1,cmp);
     for(int i=1;i <=m;++i)
    {
        if (grupa(muchie[IND[i]].x) != grupa(muchie[IND[i]].y)){
            rez+= muchie[IND[i]].c;
           add(muchie[IND[i]].x,muchie[IND[i]].y);
            VANS.push_back(IND[i]);
        }
    }
    g<<rez<<'\n'<<n-1<<'\n';
     for(int i=0;i <n-1;++i)
        g<<muchie[VANS[i]].x<<" "<<muchie[VANS[i]].y<<'\n';



    return 0;
}