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

ifstream f("zapada.in");
ofstream g("zapada.out");

int n, m, cnt, s, curent;
int t[200001];
struct mama{
    int i, j, c;
}v[200001], a[200001];

bool cmp(mama a, mama b)
{
    if(a.c < b.c)
        return true;
    return false;
}

int main()
{
    f>>n>>m;
    for(int k=1; k<=m; k++)
    {
        int x, y, t;
        f>>x>>y>>t;
        v[k].i=x;
        v[k].j=y;
        v[k].c=t;
    }
    sort(v+1, v+m+1, cmp);
    for(int i=1; i<=m; i++)
    {
        if(t[v[i].i]==0 && t[v[i].j]==0)
        {
            s+=v[i].c;
            a[++cnt].i=v[i].i;
            a[cnt].j=v[i].j;
            t[v[i].i]=t[v[i].j]=++curent;
        }
        else if(t[v[i].i]==0 || t[v[i].j]==0)
        {
            s+=v[i].c;
            a[++cnt].i=v[i].i;
            a[cnt].j=v[i].j;
            t[v[i].i]=t[v[i].j]=max(t[v[i].i], t[v[i].j]);
        }
        else if(t[v[i].i] != t[v[i].j])
        {
            s+=v[i].c;
            a[++cnt].i=v[i].i;
            a[cnt].j=v[i].j;
            int val=min(t[v[i].i], t[v[i].j]);
            int val2=max(t[v[i].i], t[v[i].j]);
            for(int j=1; j<=n; j++)
                if(t[j]==val2)
                    t[j]=val;
        }
        int gasit=0;
        for(int i=1; i<=n; i++)
            if(t[i]==1)
                gasit++;
        if(gasit==n)
        {
            g<<s<<'\n'<<cnt<<'\n';
            for(int i=1; i<=cnt; i++)
                g<<a[i].j<<" "<<a[i].i<<'\n';;
            return 0;
        }

    }

}