#include <cstdio>
#include <vector>
#include <tuple>
#include <queue>

#define INF 2000000000
#define NMAX 200000

using namespace std;

FILE *in=fopen("apm.in", "r"), *out=fopen("apm.out", "w");
int n, m;
int us[NMAX+2], af[NMAX+2], x, y, c;
vector<pair<int, int>> vp[NMAX+2];
int prim(int x)
{
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> qul; //cost, node, lastnode
    us[x]=0; //x node used
	af[1]=0;
    for(int i=0; i<vp[x].size(); i++)
    {
        qul.push({vp[x][i].second, vp[x][i].first, x});
    }
    //qul.push({mincost, newnode, x});
    while(!qul.empty())
    {
        tuple<int, int, int> tp=qul.top();
        qul.pop();
        int curnode=get<1>(tp);
        int lastnode=get<2>(tp);
        int curcost=get<0>(tp);
        if(af[curnode]==-1 && us[curnode]>curcost)
        {
            us[curnode]=curcost;
            af[curnode]=lastnode;

            for(int i=0; i<vp[curnode].size(); i++)
            {
                qul.push({vp[curnode][i].second, vp[curnode][i].first, curnode});
            }
        }
    }
	int totcost=0;
	for(int i=1; i<=n; i++)
		totcost+=us[i];
    return totcost;
}


int main()
{
    fscanf(in, "%d %d", &n, &m);
    for(int i=1; i<=m; i++)
    {
        fscanf(in, "%d %d %d", &x, &y, &c);
        vp[x].push_back({y, c});
        vp[y].push_back({x, c});
    }
	for(int i=1; i<=n; i++)
		us[i]=INF, af[i]=-1;


    fprintf(out, "%d\n%d\n", prim(1), n-1);
    for(int i=2; i<=n; i++)
    {
        fprintf(out, "%d %d\n", i, af[i]);
		//fprintf(out, "%d\n", us[i]);
    }
    return 0;
}