#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200002
#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 cmin;
vector<int> sel;

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

void kruskal();

int gaseste(int x)
{
    if(tata[x]==x) //radacina
        return x;
    tata[x]=gaseste(tata[x]);
    return tata[x];
}

int uneste(int x,int y)
{
    x=gaseste(x);
    y=gaseste(y);
    if(x!=y)
        tata[y]=x;
}

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,compar);
    kruskal();
    fout<<cmin<<'\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;
    //initializare tata
    for(i=1; i<=n; i++)
        tata[i]=i;
    for(i=1; i<=m; i++)
        //daca nu fac parte din aceeasi mt
        if(gaseste(a[i].x)!=gaseste(a[i].y))
            {
             cmin+=a[i].c;
             uneste(a[i].x,a[i].y);
             sel.push_back(i);
            }
}