#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;
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 kruskal()
{
int i,j,k,c,n1,n2;
for(i=0;i<=n;i++)
t[i]=i;
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";
for(i=0;i<sol.size();i++)
fout<<sol[i].f<<" "<<sol[i].s<<"\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();

return 0;
}