#include <fstream>
#include <vector>
#include <algorithm>
#define MaxNumbersOfNodes 200005
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

pair < int , pair < int , int > > pr[MaxNumbersOfNodes * 2];
vector < pair < int , int > > Answer;
int ds[MaxNumbersOfNodes], N, M, minCost;

int root(int x)
{
    while(ds[x] != x){
        ds[x] = ds[ds[x]];
        x = ds[x];
    }
    return x;
}

void UnionFind(int x, int y)
{
    int px = root(x);
    int py = root(y);
    ds[px] = ds[py];
}

int Kruskal()
{
    int nodeX, nodeY, costRoad;
    for(int i = 1; i <= M; i++){
        nodeX = pr[i].second.first;
        nodeY = pr[i].second.second;
        costRoad = pr[i].first;
        if(root(nodeX) != root(nodeY)){
            UnionFind(nodeX,nodeY);
            Answer.push_back(make_pair(nodeX,nodeY));
            minCost += costRoad;
        }
    }
    return minCost;
}

int main()
{
    int nodeX, nodeY, costRoad;
    cin >> N >> M;
    for(int i = 1; i <= M; i++){
        cin >> nodeX >> nodeY >> costRoad;
        pr[i] = make_pair(costRoad,make_pair(nodeX,nodeY));
    }
    sort(pr + 1, pr + M + 1);
    for(int i = 1; i <= N; i++){
        ds[i] = i;
    }
    cout << Kruskal() << "\n" << Answer.size() << "\n";
    for(int i = 0; i < Answer.size(); i++){
        cout << Answer[i].first << " " << Answer[i].second << "\n";
    }
    return 0;
}