#include <fstream>
#include <algorithm>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");
struct muchie
{
    int x,y,c;
}a[200001],sol[200001];
int T[200001],R[200001],n,cost,k,m;
int root(int start)
{
    while(T[start]!=start)
        start = T[start];
    return start;
}
void unifica(int x,int y)
{
    if(R[x]<R[y])
        T[x]=y;
    else if(R[y]<R[x])
        T[y]=x;
    else
    {
        T[x] = y;
        R[y]++;
    }
}
void kruskal()
{
    int i = 1;
    while(k < n-1)
    {
        int rx = root(a[i].x);
        int ry = root(a[i].y);
        if(rx!=ry)
        {
            k++;
            cost+=a[i].c;
            sol[k]=a[i];
            unifica(rx,ry);
        }
        ++i;
    }
}
bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>a[i].x>>a[i].y>>a[i].c;
        T[i]=i;
    }
    sort(a+1,a+m+1,cmp);
    kruskal();
    cout<<cost<<'\n';
    cout<<k<<'\n';
    for(int i=1; i<=k; i++)
        cout<<sol[i].x<<' '<<sol[i].y<<'\n';
    return 0;
}