#include <bits/stdc++.h>
#define Mmax 400001
#define Nmax 200001
//Kruskal int O(m*log m+n*n)
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie
{
    int in;
    int sf;
    int cost;
};
muchie muc[Mmax];
int sol[Mmax];
inline bool cmp(const muchie &x, const muchie &y)
{
    return x.cost<y.cost;
}
int con[Nmax];
int main()
{int n,m,k,i,j,c;
f>>n>>m;
for(k=1;k<=m;k++)
    f>>muc[k].in>>muc[k].sf>>muc[k].cost;
sort(muc+1,muc+m+1,cmp);
c=0;
int sum=0;
for(i=1;i<=n;i++)
con[i]=i;
int minn,maxx;
for(i=1;i<=m and c<n-1;i++)
    if(con[muc[i].in]!=con[muc[i].sf])
    {
        sol[++c]=i;
        sum+=muc[i].cost;
        minn=min(con[muc[i].in],con[muc[i].sf]);
        maxx=con[muc[i].in]+con[muc[i].sf]-minn;
        for(j=1;j<=n;j++)
            if(con[j]==maxx) con[j]=minn;
    }
g<<sum<<'\n'<<c<<'\n';
for(i=1;i<=c;i++)
    g<<muc[sol[i]].in<<' '<<muc[sol[i]].sf<<'\n';

    return 0;
}