#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],H[200005];
int CostMin=0;

int Find(int x)
{
    while(T[x]!=x) x=T[x];
    return x;
}
void Union(int x, int y)
{
    x=Find(x);
    y=Find(y);
    if(H[x]<H[y])
        T[x]=y;
    else if(H[y]<H[x])
            T[y]=x;
        else 
        {
            T[x]=y;
            H[y]++;
        }
}
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;
            H[i]=1;
        }
    sort(L.begin(), L.end(), cmp);
    for(int i=0; i<m;i++)
        {
            muchie M=L[i];
            if(Find(T[M.x])!=Find(T[M.y]))
            {
                CostMin+=M.cost;
                L2.push_back(M);
                Union(M.x,M.y);
            }
        }
    fout<<CostMin<<"\n"<<L2.size()<<"\n";
    for (int i=0;i<L2.size();i++)
    {
        fout<<L2[i].x<<" "<<L2[i].y<<'\n';
        
    }
    return 0;
}