#include <bits/stdc++.h>
using namespace std;
struct muchie
{
    int x,y,cost;
};
vector <muchie> L;
vector <muchie> L2;
bool cmp (muchie m, muchie n)
{
    return m.cost<=n.cost;
}
int NrSA;
int T[200005];
int CostMin=0;


ifstream fin("apm.in");
ofstream fout("apm.out");
int main()
{
    int n, m;
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x, y, cost;
        fin>>x>>y>>cost;
        L.push_back({x,y,cost});
    } 
    for (int i=1;i<=n;i++)
        T[i]=i;
    sort(L.begin(), L.end(), cmp);
    for(int i=0; i<m;i++)
        {
            muchie M=L[i];
            if(T[M.x]!=T[M.y])
            {
                L2.push_back(M);
                int Repr=T[M.y];
                CostMin+=M.cost;
                for(int j=1;j<=n;j++)
                    if(T[j]==Repr) T[j]=T[M.x];
            }
        }
    fout<<CostMin<<"\n"<<L2.size()<<"\n";
    for (int i=0;i<L2.size();i++)
    {
        fout<<L2[i].x<<" "<<L2[i].y<<'\n';
        
    }
    return 0;
}