#include <iostream>
#include <fstream>
#include <vector>
#define nmax 400001
#define inf 0x3f3f3f

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m,u,v,nr=0,ct=0,z[nmax];
int h[nmax],t[nmax];
vector < pair < int, int > > S;
struct muchie
{
    int x,y,cost;
} c[nmax];
int Find(int x)
{
    while(x != t[x])
        x=t[x];
    return x;
}
void Union(int rx, int ry)
{
    if(h[rx]==h[ry])
    {
        h[rx]++;
        t[rx]=ry;
    }
    else if(h[rx] < h[ry])
    {
        t[rx]=ry;
    }
    else t[ry]=rx;

}
int main()
{
    fin>>n>>m;
    for(int i =1 ; i <= m ; i ++)
    {
        fin>>c[i].x>>c[i].y>>c[i].cost;
    }
    for(int i =1 ; i <= n ; i++)
    {
        z[i]=i;
        t[i]=i;
    }
    for(int i =1 ; i < m ; i++)
    {
        for(int j =i+1 ; j <=m ; j ++)
            if(c[i].cost>c[j].cost)
            {
                muchie aux;
                aux=c[i];
                c[i]=c[j];
                c[j]=aux;
            }
    }

    int i=1;

    while(nr<n-1)
    {
        u=z[c[i].x];
        v=z[c[i].y];
        Find(u);
        Find(v);
        if(u!=v)
        {
            nr++;
            ct=ct+c[i].cost;
            S.push_back(make_pair(c[i].x,c[i].y));
            Union(u,v);
        }
        i++;
    }
    fout<<ct<<'\n';
    fout<<nr<<'\n';
    for(int i =0; i < nr; i ++)
        fout<<S[i].first<<" "<<S[i].second<<'\n';

    return 0;
}