#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){};
    inline bool operator()(const Edge& a, const Edge& b)
    {
        return w[a] < w[b];
    }
};
inline int find(int x, vector<int>& t)
{
    if (t[x] == x) return x;
    t[x] = find(t[x], t);
    return t[x];
}
inline void merge(int x, int y,vector<int>& t)
{
    t[find(x, t)] = find(y, t);
}
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(int i=1;i<g.Edges.size()-1;i++)
        for(int j=i+1;j<g.Edges.size();j++)
            if(w[g.Edges[j]] < w[g.Edges[i]])
                swap(g.Edges[j],g.Edges[i]);
    for(const auto& edge : g.Edges)
    {
        int u=edge.first, v=edge.second;
        if(find(u, tree) != find(v, tree))
        {
            MinSpanningTree.push_back(edge);
            merge(u, v, tree);
        }
    }
    return MinSpanningTree;
}
int main()
{
    Graph g;
    Weight w;
    int NrEdges,x,y,c;
    long long MSTCost=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 MST = Kruskal(g,w);
    for(const auto& edge : MST)
    {
        MSTCost+=w[edge];
        out<<edge.first<<" "<<edge.second<<"\n";
    }
    fout<<MSTCost<<"\n"<<MST.size()<<"\n"<<out.str();
    return 0;
}