#include <fstream>
#include <algorithm>
#include <vector>
#define MMAX 400001
#define NMAX 200001
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
struct muchie
{
    int x,y,c;
};
muchie G[MMAX];
long long int cmin;
int g[NMAX],rg[NMAX];
int rez[MMAX],nrez;

void citire();
void kruskal();
int gaseste(int x);
void uneste(int x,int y);
bool compar(muchie a,muchie b)
{
    return a.c<b.c;
}
int main()
{
    citire();
    kruskal();
    fout<<cmin<<'\n';
    fout<<nrez<<'\n';
    for(int i=1;i<=nrez;i++)
        fout<<G[rez[i]].x<<' '<<G[rez[i]].y<<'\n';
    return 0;
}
void citire()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
}
void kruskal()
{
    int i;
    for(i=1;i<=n;i++) {g[i]=i; rg[i]=1;}
    sort(G+1,G+m+1,compar);
    for(i=1;i<=m;i++)
        if(gaseste(G[i].x)!=gaseste(G[i].y))
        {
            cmin+=G[i].c;
            uneste(gaseste(G[i].x),gaseste(G[i].y));
            rez[++nrez]=i;
        }
}
int gaseste(int x)
{
    int radacina,y;
    //gasim radacina
    for(radacina=x;g[radacina]!=radacina;radacina=g[radacina]);
    //path comprehension
    while(g[x]!=x)
    {
        y=g[x];
        g[x]=radacina;
        x=y;
    }
    return radacina;
}
void uneste(int x,int y)
{
    if(rg[x]>rg[y]) g[y]=x;
    else g[x]=y;
    if(rg[x]==rg[y]) rg[y]++;
}