#include <iostream>
	
#include <fstream>
	
#include <algorithm>
	
#include <vector>
	
#define mp make_pair
	
using namespace std;
	
ifstream f("apm.in");
	
ofstream g("apm.out");
	
 
	
const int maxn=400005;
	
struct apm
	
{
	
    int x,y,cost;
	
}APM[maxn];
	
vector <pair <int,int> > Gans;
	
int N,M,X[maxn],Y[maxn],C[maxn];
	
int GRUP[maxn],nr_grup[maxn];
	
int cmp (apm a, apm b)
	
{
	
    if(a.cost<b.cost)
	
        return 1;
	
    return 0;
	
}
	
int grupa(int x)
	
{
	
    int R, y;
	
    for (R = x; GRUP[R] != R; R = GRUP[R]);
	
	
    return R;
	
}
	
void reunire(int x, int y)
	
{
	
    if (nr_grup[x] > nr_grup[y])
	
        GRUP[y] = x;
	
    else GRUP[x] = y;
	
 
	
    if (nr_grup[x] == nr_grup[y]) nr_grup[y]++;
	
}
	
int main()
	
{
	
    int i,ans=0;
	
    f>>N>>M;
	
    for (i=1;i<=M;i++)
	
    {
	
        f>>APM[i].x>>APM[i].y>>APM[i].cost;
	
    }
	
    sort(APM+1,APM+M+1,cmp);
	
 
	
    for (int i=1;i<=N;i++) {nr_grup[i]=1;GRUP[i]=i;}
	
 
	
    for (i=1;i<=M;i++)
	
    {
	
        if (grupa(APM[i].x) != grupa(APM[i].y) )
	
        {
	
            reunire(grupa(APM[i].x),grupa(APM[i].y));
	
            ans+=APM[i].cost;
	
            Gans.push_back(mp(APM[i].x,APM[i].y));
	
        }
	
    }
	
    g<<ans<<'\n';
	
    g<<N-1<<'\n';
	
    for (i=0;i<N-1;i++)
	
        g<<Gans[i].first<<" "<<Gans[i].second<<'\n';
	
 
	
 
	
}