#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int maxn = 200001;

#define mp make_pair
#define pb push_back
#define inf 0x3f3f3f3f

int d[maxn];
int inq[maxn], kesz[maxn], p[maxn];

struct cmp
{
    bool operator ()(const int i, const int j) const
    {
	return d[i] > d[j];
    }
};

int n, m; 
vector<pair<int, int> > g[maxn];

priority_queue<int, vector<int>, cmp> Q;
int tcost;

void read()
{
    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].pb(mp(y,c));
	g[y].pb(mp(x,c));
    }
}

void prim()
{ 
    memset(d, 0x3f, sizeof(d));
    d[1] = 0; Q.push(1); kesz[1] = 1; 

    int t = n;

    while (!Q.empty())
    {
	int akt = Q.top(); Q.pop();
	tcost += d[akt];
	kesz[akt] = 1;
	--t;
	for (int i = 0; i < g[akt].size(); ++i)
	{
	    int next = g[akt][i].first; int cost = g[akt][i].second;
	    if (kesz[next]) continue;
	    if (d[next] > cost) 
	    {
		d[next] = cost; 
		p[next] = akt;
		if (!inq[next])
		{
		    inq[next] = 1;
		    Q.push(next);
		}
	    }
	}
	inq[akt] = 0;
	if (!t) break;
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    read();
    prim();
    printf("%d\n", tcost);
    printf("%d\n", n - 1);
    for (int i = 2; i <= n; ++i)
	printf("%d %d\n", p[i], i);

    return 0;
}