//Include
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

FILE *in, *out;

//Define
#define edge pair<int, pair<int, int> >
#define cost first
#define from second.first
#define to second.second
#define mp make_pair
#define pb push_back

//Constante
const int sz = (int)2e5+1;

//Functii
int getRoot(int node);

//Variabile
int nodes, edges;
int sum;
int father[sz];
vector < pair<int,int> > answer;

priority_queue <edge, vector<edge>, greater<edge> > heap;

//Main
int main()
{
	in = fopen("apm.in", "rt");
	out = fopen("apm.out", "wt");
    fscanf(in,"%d%d", &nodes, &edges);
    int rFrom, rTo, rCost;
    for(int i=1; i<=edges; ++i)
    {
        fscanf(in,"%d%d%d", &rFrom, &rTo, &rCost);
        heap.push(mp(rCost, mp(rFrom, rTo)));
    }

    while(!heap.empty())
    {
        edge current = heap.top();
        heap.pop();
        int node1 = current.from;
        int node2 = current.to;
        int root1 = getRoot(node1);
        int root2 = getRoot(node2);

        if(root1 != root2)
        {
            answer.pb(current.second);
            sum += current.cost;
            father[root2] = root1;
        }
    }
    fprintf(out,"%d\n", sum);
    fprintf(out,"%d\n", answer.size());
    vector< pair<int,int> >::iterator it, end = answer.end();
    for(it = answer.begin(); it!=end; ++it)
    {
        fprintf(out,"%d %d",it->first, it->second);
        fprintf(out,"\n");
    }

	fclose(in);
	fclose(out);
	return 0;
}

int getRoot(int node)
{
    return (father[node])? father[node] = getRoot(father[node]) : node;
}