#include <fstream>
#include <vector>
#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;
};

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

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;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort(a+1,a+1+m,cmp);
    kruskal();
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(i=0; i<sel.size(); i++)
        fout<<a[sel[i]].x<<' '<<a[sel[i]].y<<'\n';
    return 0;
}

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