#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 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);
}
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(find(u, tree) != find(v, tree))
        {
            MinSpanningTree.push_back({u,v});
            MSTcost+=edge.second;
            merge(u, v, tree);
        }
    }
}
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;
}