#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
#define nmax 200003
int n,m,c[nmax],cost_apm;
bool use[nmax];
struct muchie
{
    int x,y,cost;
} edge[nmax];
bool cmp(const muchie a,const muchie b)
{
    return a.cost<b.cost;
}
int group(int i)
{
    if(i==c[i]) return i;
    c[i]=group(c[i]);
    return c[i];
}
void uneste(int i,int j)
{
    c[group(i)]=group(j);
}
void Kruskal()
{
    int step=0;
    for(int i=1; i<=n; i++)
        c[i]=i;
    for(int i=1; i<=m && step!=n-1; i++)
        if(group(edge[i].x) != group(edge[i].y))
        {
            uneste(edge[i].x,edge[i].y);
            cost_apm+=edge[i].cost;
            step++;
            use[i]=true;
        }
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>edge[i].x>>edge[i].y>>edge[i].cost;
    sort(edge+1,edge+m+1,cmp);
    Kruskal();
    g<<cost_apm<<'\n'<<n-1<<'\n';
    for(int i=1; i<=m; i++)
        if(use[i]) g<<edge[i].x<<" "<<edge[i].y<<'\n';
    return 0;
}