#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

int v[200001],i,n,m,s,nr,p,q;

struct nod
{
    int x,y,z;
};

nod a[400001];

int root(int x)
{
    if (v[x]==x)
        return x;
    else return root(v[x]);
}

bool cmp(nod a,nod b)
{
    return (a.z<b.z);
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f >> n >> m;
    for (i=1;i<=m;i++)
    {
        f >> a[i].x >> a[i].y >> a[i].z;
    }
    //sort(&a[1],&a[n+1],cmp);
    bool ok=false;nod aux;
	while (!ok)
	{
		ok=true;
		for (i=1;i<m;i++)
			if (a[i].z>a[i+1].z)
			{
				aux=a[i];
				a[i]=a[i+1];
				a[i+1]=aux;
				ok=false;
			}
	}
	for (i=1;i<=n;i++)
        v[i]=i;
    for (i=1;i<=m;i++)
	{
		p=root(a[i].x);
		q=root(a[i].y);
	    if (p!=q)
        {
            a[++nr]=a[i];
            v[p]=q;
            s+=a[i].z;
		}
	}
    if (nr!=n-1)
		g << -1;
	else 
	{
		g << s << "\n";
		g << n-1 << "\n";
		for (i=1;i<=nr;i++)
			g << a[i].x << ' ' << a[i].y << "\n";
    }
	return 0;
}