#include <algorithm>
#include <fstream>
#include <list>

using namespace std;

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

#define limn 200010
int n,m;
struct muchie{int x,y,c;} g[limn];
int dad[limn];
long long s=0;
list <int> ans;

bool cmp(muchie A, muchie B)
{
    if(A.c < B.c)   return true;
    return false;
}

int get_dad(int x)
{
    if(dad[x]!=x)   dad[x]=get_dad(dad[x]);
    return dad[x];
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; i++)
        fin>>g[i].x>>g[i].y>>g[i].c;
    for(int i=1; i<=n; i++) dad[i]=i;
    sort(g+1, g+m+1, cmp);

    for(int i=1; i<=m; i++)
        if(get_dad(g[i].x) != get_dad(g[i].y))
        {
            dad[get_dad(g[i].x)] = get_dad(g[i].y);
            s += g[i].c;
            ans.push_back(i);
        }

    fout<<s<<'\n';
    fout<<ans.size()<<'\n';
    for(auto it:ans)
        fout<<g[it].x<<' '<<g[it].y<<'\n';

    fin.close();
    fout.close();
    return 0;
}