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

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

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

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 rootX = Root(X), rootY = Root(Y);
    ds[X] = ds[Y];
}

int Kruskal()
{
    int nodeX, nodeY, costRoad, rootX, rootY;
    for(int i = 1; i <= M; i++){
        nodeX = Edges[i].second.first;
        nodeY = Edges[i].second.second;
        costRoad = Edges[i].first;
        rootX = Root(nodeX);
        rootY = Root(nodeY);
        if(rootX != rootY){
            UnionFind(rootX,rootY);
            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;
        Edges[i] = make_pair(costRoad,make_pair(nodeX,nodeY));
    }
    sort(Edges + 1,Edges + 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;
}