#include <fstream>
#include <cstdlib>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct Edge{
int src,dest,weight;
};

struct Graph{
int V,E;

struct Edge* edge;
};

struct Graph* createGraph(int V, int E){
struct Graph* graph = new Graph;

graph->V = V;
graph->E = E;
graph->edge = new Edge[E];

return graph;
};

struct subset{
int parent, rank;
};

int find(struct subset subsets[], int i){
if(subsets[i].parent != i)
    subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

void Union(struct subset subsets[], int x, int y){
int xroot = find(subsets, x);
int yroot = find(subsets, y);

if(subsets[xroot].rank > subsets[yroot].rank)
    subsets[yroot].parent = xroot;
else if(subsets[xroot].rank < subsets[yroot].rank)
    subsets[xroot].parent = yroot;
else {
    subsets[yroot].parent = xroot;
    subsets[xroot].rank++;
}
}

int compare(const void* a, const void* b){
struct Edge* a1 = (struct Edge*)a;
struct Edge* b1 = (struct Edge*)b;

if(a1->weight == b1->weight)return 0;
return (a1->weight > b1->weight) ? 1 : -1;
}

void KruskalMST(struct Graph* graph){
int V = graph->V;
struct Edge result[V];
int e = 0;
int i = 0;

qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);

struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));

for(int v = 0; v < V; ++v){
    subsets[v].parent = v;
    subsets[v].rank = 0;
}
int total = 0;

while(e < V - 1){
    struct Edge next_edge = graph->edge[i++];

    int x = find(subsets, next_edge.src);
    int y = find(subsets, next_edge.dest);

    if(x != y){
        result[e++] = next_edge;
        total += next_edge.weight;
        Union(subsets,x,y);
    }
}
g<<total<<'\n';
g<<e<<'\n';
for(int i=0;i<e;++i)
    g<<++result[i].src<<" "<<++result[i].dest<<'\n';

}


int main(){
int n,m;

f>>n>>m;

struct Graph* graph = createGraph(n,m);

for(int i=0;i<m;++i){
    f>>graph->edge[i].src>>graph->edge[i].dest>>graph->edge[i].weight;
    graph->edge[i].src--;
    graph->edge[i].dest--;
}

    KruskalMST(graph);

return 0;
}