#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back


#define  max 400100
using namespace std;
int gr[max], x[max], y[max],c[max];
int n,m,ans,ind[max];
vector<int> vans;
int grupa (int i)
{
if(gr[i]==i) return i;
gr[i]=grupa(gr[i]);
return gr[i];    
}
bool cmpf(int i, int j)
{
     return (c[i]<c[j]);
     }
void reuniune(int i, int j)
{
     gr[grupa(i)]=grupa(j);
     }

int main()
{
    int i,j;
ifstream f("apm.in");
ofstream g("apm.out");
f>>n>>m;
for (i=1;i<=m;i++)
{
f>>x[i]>>y[i]>>c[i];
ind[i]=i;
}    

for(i=1;i<=n;i++)
gr[i]=i;
sort(ind + 1,ind + m+ 1,cmpf);
for(i=1;i<=m;i++)
{
if (grupa(x[ind[i]])!=grupa(y[ind[i]])) 
{
  ans =ans+ c[ind[i]];
  reuniune(x[ind[i]],y[ind[i]]);
  vans.pb(ind[i]);                                      
} }
g<<ans<<"\n";
g<<n-1<<"\n";
                
g<<x[vans[i]]<<" "<<y[vans[i]]<<"\n";
return 0;
        
}