#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector<pair<pair<int, int>, int> > G;
vector<pair<int, int>> MinSpanningTree;
int NrVertexes, NrEdges, x, y, c, MSTcost;
inline bool cmp(const pair<pair<int, int>, int>& a, const pair<pair<int, int>, int>& b)
{
    return a.second < b.second;
}
void Kruskal()
{
    vector<int> tree;
    tree.reserve(NrVertexes + 1);
    for(int i=1;i<=NrVertexes;i++)
        tree[i]=i;
    sort(G.begin(),G.end(),cmp);
    for(const auto& edge : G)
    {
        int u=edge.first.first, v=edge.first.second;
        if(tree[u] != tree[v])
        {
            MinSpanningTree.push_back({u,v});
            MSTcost+=edge.second;
            for(int i=1;i<=NrVertexes;i++)
                if(i!=u&&tree[i]==tree[u])
                    tree[i] = tree[v];
            tree[u] = tree[v];
        }
    }
}
int main()
{
    fin>>NrVertexes>>NrEdges;
    for(int i=1;i<=NrEdges;i++)
    {
        fin>>x>>y>>c;
        G.push_back({{x,y},c});
    }
    Kruskal();
    fout<<MSTcost<<"\n"<<NrVertexes-1<<"\n";
    for(const auto& edge : MinSpanningTree)
        fout<<edge.first<<" "<<edge.second<<"\n";
    return 0;
}