#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct muchie {
    int x, y, cost;
};

struct CompareCost {
    bool operator()(muchie const& m1, muchie const& m2) {
        return m1.cost > m2.cost; // Min-heap based on cost
    }
};
int costTotal;
priority_queue<muchie, vector<muchie>, CompareCost> pq;
vector<int> repr(100001, -1);
vector<pair<int,int>> mst;
int n, m;
void kruskal(int nod)
{
    repr[nod]=nod;
    while(!pq.empty())
    {
        muchie m=pq.top();
        pq.pop();
        if(repr[m.x]!=repr[m.y])
        {
            mst.push_back({m.x,m.y});
            costTotal+=m.cost;
            int a=repr[m.x];
            int b=repr[m.y];
            for(int i=1;i<=n;i++)
            {
                if(repr[i]==b)
                {
                    repr[i]=a;
                }
            }
        }
    }

}
int main()
{
    in>>n>>m;
    for(int i=1;i<=n;i++)
        repr[i]=i;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        in>>x>>y>>z;
        pq.push({x,y,z});

    }
    kruskal(1);
    out<<costTotal<<'\n'<<n-1<<'\n';
    for(int i=0;i<mst.size();i++)
    {
        out<<mst[i].first<<' '<<mst[i].second<<'\n';
    }
    

    in.close();
    out.close();

    return 0;
}