#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector <int> M;
int x[400100],y[400100],c[400100],G[400100],ind[400100];

int grupa(int i);

bool comp(int i, int j)
{
    return c[i]<c[j];
}
int main()
{
    int n,m,i,cost=0;
    fin>>n>>m;
    for(i=1;i<=n;i++) G[i]=i;
    for(i=1;i<=m;i++)
    {
        fin>>x[i]>>y[i]>>c[i];
        ind[i]=i;
    }
    sort(ind+1,ind+1+m,comp);
    for(i=1;i<=m;i++)
    {
        if( grupa(x[ind[i]])!= grupa( y[ind[i]]))
        {
            cost+=c[ind[i]];
            G[grupa(x[ind[i]])]=grupa(y[ind[i]]);
            M.push_back(ind[i]);
        }
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<x[M[i]]<<" "<<y[M[i]]<<'\n';
    return 0;
}

int grupa(int i)
{
	if (G[i]==i)
         return i;
	G[i]=grupa(G[i]);
        return G[i];
}