// Include
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

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

// Definitii
#define edge pair<int, pair<int, int> >
#define cost first
#define from second.first
#define to second.second

// 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()
{
    freopen("apm.in", "rt", stdin);
    freopen("apm.out", "wt", stdout);
    scanf("%d%d",&nodes,&edges);
    for(int i=1; i<=edges; ++i)
    {
        int rFrom, rTo, rCost;
        scanf("%d%d%d",&rFrom, &rTo, &rCost);
        heap.push(make_pair(rCost, make_pair(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)
        {
            father[root2] = root1;
            sum += current.cost;
            answer.push_back(current.second);
        }
    }
    printf("%d\n%d\n",sum, nodes-1);
    vector< pair<int, int> >::iterator it, end = answer.end();
    for(it=answer.begin(); it!=end; ++it)
        printf("%d %d\n",it->first, it->second);
    fclose(stdin);
    fclose(stdout);
    return 0;
}

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