#include <fstream>
#include <cstdlib>

using namespace std;

ifstream f("kruskal.in");
ofstream g("kruskal.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';
}
return;
}

int main(){
ios_base::sync_with_stdio(false);
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;
}