#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

#define lim 200010
struct muchie {int x,y,cost;} G[2*lim];
int n,m;
int dad[lim],dr,sum;
pair <int, int> sol[lim];

bool cmp (muchie A, muchie B)
{
    return A.cost<B.cost;
}

int get_dad (int x)
{
    if (dad[x]!=x)  dad[x] = get_dad(dad[x]);
    return dad[x];
}

int main()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++)
        fin>>G[i].x>>G[i].y>>G[i].cost;

    sort (G+1, G+m+1, cmp);
    for (int i=1; i<=n; i++)    dad[i]=i;

    sum=0;
    for (int i=1; i<=m; i++)
        if (get_dad(G[i].x) != get_dad(G[i].y))
        {
            dad[get_dad(G[i].y)] = get_dad (G[i].x);
            sum+=G[i].cost;
            sol[++dr]={G[i].x, G[i].y};
        }

    fout<<sum<<'\n'<<dr<<'\n';
    for (int i=1; i<=dr; i++)
        fout<<sol[i].first<<' '<<sol[i].second<<'\n';
    return 0;
}