#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

const int dim = 100001;
int n,m,op,t[dim],cost;

struct muchie
{
    int x,y,c;
} a[dim];
vector <pair<int,int>> sol;

int cmp (muchie a, muchie b)
{
    return a.c < b.c;
}

int radacina (int x)
{
    int r=x,j;
    while(t[r]!=0)
    {
        r=t[r];
    }
    while(t[x]!=0)
    {
        j=t[x];
        t[x]=r;
        x=j;
    }
    return r;
}

int main()
{
    fi>>n>>m;
    for(int i = 1 ; i<=m ; i++)
        fi>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+m+1,cmp);

   // for(int i = 1 ; i<=m ; i++)
    //    fo<<" "<<a[i].x<<" "<<a[i].y<<" "<<a[i].c<<'\n';

    for(int i = 1 ; i<=m ; i++)
    {
        int r1=radacina(a[i].x);
        int r2=radacina(a[i].y);
        if (r1 != r2)
        {
            t[r1]=r2;
            sol.push_back({a[i].x,a[i].y});
            cost+=a[i].c;
        }
    }

    fo<<cost<<'\n';
    fo<<sol.size()<<'\n';
    for(auto p : sol)
        fo<<p.first<<" "<<p.second<<'\n';

    return 0;
}