#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct vec
{
    int x,y,cost;
};
int n,m;
vector<vec> v;
vector<pair<int,int> > sol;
int costmin,nrsol;
ifstream fin("apm.in");
ofstream fout("apm.out");
int TT[200005],RG[200005];
bool cmp(vec x,vec y)
{
    return x.cost<y.cost;
}
void unite(int x,int y)
{
    if(RG[x]>RG[y])
        {TT[y]=x;}
    if(RG[x]<RG[y])
    {TT[x]=y;}
    if(RG[x]==RG[y])
    {
        TT[x]=y;
        RG[y]++;
    }
}
int gas(int x)
{
    while(x!=TT[x])
        x=TT[x];

    return x;
}
void afisrez()
{
    fout<<costmin<<endl;
    fout<<sol.size()<<endl;
    for(int i=0;i<sol.size();i++)
    {
        fout<<sol[i].first<<" "<<sol[i].second<<endl;
    }
}
void kruskal()
{
    sort(&v[0],&v[m],cmp);
    for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }
    int i=0;
    while(nrsol<n-1)
    {
        int x=v[i].x;
        int y=v[i].y;
        int radx=gas(v[i].x);
        int rady=gas(v[i].y);
        if(radx!=rady)
        {   nrsol++;
            unite(radx,rady);
            costmin=costmin+v[i].cost;
            sol.push_back(make_pair(v[i].x,v[i].y));
        }
    i++;
    }

}
int main()
{   fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        vec k;
        fin>>k.x>>k.y>>k.cost;
        v.push_back(k);
    }
    kruskal();
    afisrez();
}