#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(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;
}
vector<Edge> Prim(Graph g, Weight w)
{
    vector<Edge> MinSpanningTree;
    vector<int> Vertexes;
    vector<Edge> Edges(g.Edges);
    int f1,f2;

    compare cmp{w};
    sort(Edges.begin(), Edges.end(), cmp);
    auto edge=Edges.begin();
    MinSpanningTree.push_back(*edge);
    Vertexes.push_back(edge->first);
    Vertexes.push_back(edge->second);
    Edges.erase(edge);
    while(MinSpanningTree.size()!=g.NrVertexes-1)
    {
        edge=Edges.begin();
        f1=find(Vertexes.begin(), Vertexes.end(), edge->first) != Vertexes.end();
        f2=find(Vertexes.begin(), Vertexes.end(), edge->second)!= Vertexes.end();
        while(f1+f2!=1)
        {
            edge++;
            f1=find(Vertexes.begin(), Vertexes.end(), edge->first) != Vertexes.end();
            f2=find(Vertexes.begin(), Vertexes.end(), edge->second)!= Vertexes.end();
        }
        MinSpanningTree.push_back(*edge);
        if(!f1) Vertexes.push_back(edge->first);
        if(!f2) Vertexes.push_back(edge->second);
        Edges.erase(edge);
    }
    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);
    auto MST = Prim(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;
}