#include <bits/stdc++.h>

using namespace std;

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

struct edge
{
    int x,y,c;
}sol[100001];



struct cmp
{
    bool operator() (const edge &a, const edge &b)
    {
        if(a.c==b.c)
            return a.x<=b.x;
        return a.c<b.c;
    }
};

set <edge,cmp> g;

int rad[100001];

int u_find(int i)
{
    if(rad[i]==0)
        return i;
    return u_find(rad[i]);
}

void u_union(int x,int y)
{
    int i=u_find(x),j=u_find(y);
    rad[j]=i;
}

int main()
{
    int n,m,i,t=0,s=0,nrs=0;
    edge aux;
    in>>n>>m;
    for(i=1;i<=m;++i)
    {
        in>>aux.x>>aux.y>>aux.c;
        g.insert(aux);
    }
    for(i=1;i<=m && t<n;i++)
    {
        aux=*g.begin();
        g.erase(g.begin());
        if(u_find(aux.x)!=u_find(aux.y))
        {
            t++;
            s=s+aux.c;
            u_union(aux.x,aux.y);
            sol[++nrs].x=aux.x;
            sol[nrs].y=aux.y;
            sol[nrs].c=aux.c;
        }
    }
    out<<s<<"\n"<<nrs<<"\n";
    for(i=1;i<n;i++)
        out<<sol[i].x<<" "<<sol[i].y<<"\n";
    return 0;
}