#include <fstream>
#include <vector>
#include <queue>
#define NMAX 200002
#include <algorithm>
#define MMAX 400002

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

int n,m;

struct muchie
{
    int x,y,c;
    friend bool operator < (muchie a,muchie b);
};

bool operator < (muchie a,muchie b)
{
    return a.c>b.c;
}

int tata[NMAX];
int h[NMAX];
void kruskal();
vector<muchie> sel;
int cost;
priority_queue<muchie> a;

int Find(int x)
{
    if(tata[x]==x) return x;
    tata[x]=Find(tata[x]);
    return tata[x];
}

void Union(int x,int y)
{
    int rx=Find(x);
    int ry=Find(y);
    if(h[rx]>h[ry])
        tata[ry]=rx;
        else
        if(h[rx]<h[ry])
            tata[rx]=ry;
            else
            {
                tata[ry]=rx;
                h[rx]++;
            }
}

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

int main()
{
    int i;
    muchie aux;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        {
         fin>>aux.x>>aux.y>>aux.c;
         a.push(aux);
        }
    kruskal();
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=0; i<sel.size(); i++)
        fout<<sel[i].x<<' '<<sel[i].y<<'\n';
    return 0;
}

void kruskal()
{
    int i,nrsel;
    muchie aux;
    //initializare tata
    for(i=1; i<=n; i++)
        tata[i]=i;
    nrsel=0; i=1;
    while(nrsel<n-1)
    {
        aux=a.top(); a.pop();
        if(Find(aux.x)!=Find(aux.y))
            {
             cost+=aux.c;
             Union(aux.x,aux.y);
             sel.push_back(aux);
             nrsel++;
            }
        i++;
    }
}