#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;
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[y]=x;
        RG[x]++;
    }
}
int gas(int x)
{
    while(TT[x]!=x)
        x=TT[x];
    return x;
}
void afisrez()
{
    fout<<costmin<<endl;
    fout<<n-1<<endl;
    for(int i=0;i<n-1;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;
    }
    for(int i=0;i<v.size();i++)
    {
        if(gas(TT[v[i].x])!=gas(TT[v[i].y]))
        {
            unite(TT[v[i].x],TT[v[i].y]);
            costmin+=v[i].cost;
            sol.push_back(make_pair(v[i].x,v[i].y));
        }
    }

}
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();
}