#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

FILE *in = fopen("kruskal.in","r");
FILE *out = fopen("kruskal.out","w");

typedef std::pair<int, int> iPair;

class DisjointSets {
public:
    int *parent, *rnk;
    int n;

    DisjointSets(int n) {
        this->n = n;
        parent = new int[n+1];
        rnk = new int[n+1];

        for (int i = 0; i <= n; i++) {
            rnk[i] = 0;
            parent[i] = i;
        }
    }

    int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    void merge(int x, int y)
    {
        x = find(x), y = find(y);

        if (rnk[x] > rnk[y]) {
            parent[y] = x;
        }
        else {
            parent[x] = y;
        }

        if (rnk[x] == rnk[y]) {
            rnk[y]++;
        }
    }
};

class Graph {
public:
    int V;
    std::vector< std::pair<int, iPair> > edges;

    Graph(int V)
    {
        this->V = V;
    }

    void addEdge(int u, int v, int w)
    {
        edges.push_back({w, {u, v}});
    }


    void kruskal(){
        int mst_wt = 0;
        int mst_edges = 0;
        std::vector<std::pair<int,int>> mst_used_edges;

        std::sort(edges.begin(), edges.end());

        DisjointSets ds(V);

        std::vector< std::pair<int, iPair> >::iterator it;

        for (it=edges.begin(); it!=edges.end(); it++)
        {
            int u = it->second.first;
            int v = it->second.second;

            int set_u = ds.find(u);
            int set_v = ds.find(v);

            if (set_u != set_v)
            {
                mst_used_edges.push_back({u,v});
                mst_wt += it->first;
                mst_edges++;
                ds.merge(set_u, set_v);
            }
        }

        fprintf(out,"%d\n%d\n",mst_wt,mst_edges);
        for(int i = 0; i < mst_used_edges.size(); i++) {
            fprintf(out,"%d %d\n",mst_used_edges[i].first,mst_used_edges[i].second);
        }
    }
};



int main() {
    int numberOfNodes, numberOfEdges;

    fscanf(in,"%d %d",&numberOfNodes,&numberOfEdges);

    Graph g(numberOfNodes);

    for(int i = 0; i < numberOfEdges; i++) {
        int start, end, cost;
        fscanf(in,"%d %d %d",&start,&end,&cost);
        g.addEdge(start,end,cost);
    }

    g.kruskal();

    fclose(in);
    fclose(out);
    
    return 0;
}