#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
typedef pair<int, int> Edge;
typedef map<Edge, int> Weight;
typedef struct
{
    vector<Edge> Edges;
    int NrVertexes;
} Graph;
struct compare
{
    Weight& w;
    compare(Weight w): w(w){};
    bool operator()(const Edge& a, const Edge& b)
    {
        return w[a] < w[b];
    }
};
vector<Edge> Kruskal(Graph g, Weight w)
{
    vector<int> tree(g.NrVertexes+1);
    vector<Edge> MinSpanningTree;
    for(int i=1;i<=g.NrVertexes;i++)
        tree[i]=i;
    compare cmp{w};
    sort(g.Edges.begin(), g.Edges.end(), cmp);
    for(const auto& edge : g.Edges)
    {
        if(tree[edge.first] != tree[edge.second])
        {
            int u=edge.first, v=edge.second;
            MinSpanningTree.push_back(edge);
            for(int i=1;i<=g.NrVertexes;i++)
                if(i!=u&&tree[i]==tree[u])
                    tree[i] = tree[v];
            tree[u] = tree[v];
        }

    }
    return MinSpanningTree;
}
int main()
{
    Graph g;
    Weight w;
    int NrEdges,x,y,c;
    long long MSPCost=0;
    ostringstream out;
    fin>>g.NrVertexes>>NrEdges;
    for(int i=0;i<NrEdges;i++)
    {
        fin>>x>>y>>c;
        g.Edges.push_back({x, y});
        w[{x, y}]=c;
    }
    auto MSP = Kruskal(g,w);
    for(const auto& edge : MSP)
    {
        MSPCost+=w[edge];
        out<<edge.first<<" "<<edge.second<<"\n";
    }
    fout<<MSPCost<<"\n"<<MSP.size()<<"\n"<<out.str();
    return 0;
}