#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int s[200000],n,m,cost=0;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edges{int x,y,z;}M[400000];

vector<pair<int,int> >sol;
void read()
{ int i;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    fin>>M[i].x>>M[i].y>>M[i].z;

}
bool cmp(edges a,edges b)
{ return a.z<b.z;
}
void unif(int a,int b)
{
    int aux=s[b],i;
    for(i=1;i<=n;i++)
    if(s[i]==aux) s[i]=s[a];
}
void apm()
{
    int i;
    for(i=1;i<=n;i++)
    s[i]=i;
    sort(M+1,M+m+1,cmp);
    for(i=1;i<=m;i++)
    if(s[M[i].x]!=s[M[i].y]) {unif(M[i].x,M[i].y);
                              cost+=M[i].z;
                              sol.push_back(make_pair(M[i].x,M[i].y));}
}


int main()
{
    read();
    apm();
    fout<<cost<<endl<<sol.size()<<endl;

for( vector<pair<int,int> >::iterator it=sol.begin();it!=sol.end();it++)
        fout<<it->first<<" "<<it->second<<"\n";
}