#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

#define mp make_pair
#define maxn 200000
#define INF 0x7fffffff

int n, m;

////////////PT HEAP//////////////
int v[maxn], h[maxn*2], pos[maxn], l;
/////////////////////////////////

vector<pair <int, int> > G[maxn], vf;
int v2[maxn], s;

void citire()
{
	freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1;i <= m; ++i)
    {
        int x,y,c;
        scanf("%d %d %d", &x, &y, &c);
        G[x].push_back(mp(y,c));
        G[y].push_back(mp(x,c));
    }
}

void downheap(int i)
{
    while((i * 2 <= l) && ((v[h[i]] > v[h[i * 2]]) || (v[h[i]] > v[h[i * 2 + 1]])))
    {
        if (v[h[i * 2]] < v[h[i * 2 + 1]] || i * 2 + 1 > l)
        {
            swap(h[i], h[i * 2]);
            swap(pos[h[i]], pos[h[i * 2]]);
            i *= 2;
        }
        else
        {
            swap(h[i], h[i * 2 + 1]);
            swap(pos[h[i]], pos[h[i * 2 + 1]]);
            i = i * 2 + 1;
        }
    }
}

void upheap(int i)
{
    while(i > 1 && v[h[i]] < v[h[i / 2]])
    {
        swap(h[i],h[i / 2]);
        swap(pos[h[i]],pos[h[i / 2]]);
        i = i / 2;
    }
}

void add_H(int nod)
{
	h[++l] = nod;
	pos[nod] = l;
	upheap(l);
}

int get_del_root()
{
	int radacina = h[1];
	swap(h[1], h[l]);
	swap(pos[h[1]], pos[h[l]]);
	l--;
	downheap(1);
	pos[radacina] = 0;
	return radacina;
}

void bagaNODU(int x)
{
    for(int i=0;i < G[x].size();i++)
    {
        int nod = G[x][i].first;
        int cost = G[x][i].second;
        v[nod] = min(v[nod],cost);
        if (v[nod] == cost)
			v2[nod] = x;
    }
}

void prim()
{
	for(int i=1;i<n;i++)
    {
        int x = get_del_root();
        bagaNODU(x);
        s += v[x];
        vf.push_back(mp(x,v2[x]));
        for(int j = 0;j < G[x].size(); ++j)
        {
            int nod = G[x][j].first;
            if (pos[nod]) upheap(pos[nod]);
        }
    }
}

int main()
{
	citire();

	for(int i=2;i<=n;i++) v[i] = INF;

	bagaNODU(1);
	for(int i=2;i<=n;i++)
	{
		add_H(i);
	}

	prim();

	printf("%d\n",s);
    printf("%d\n",n-1);
    for(int i = 0;i < n - 1; ++i)
        printf("%d %d\n",vf[i].first,vf[i].second);

	return 0;
}