#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct vec
{
    int x,y,cost;
}v[400005];
int n,m;
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;
}
int main()
{   fin>>n>>m;
    for(int i=1;i<=m;i++)
     fin>>v[i].x>>v[i].y>>v[i].cost;
 for(int i=1;i<=n;i++)
    {
        TT[i]=i;
        RG[i]=1;
    }

    sort(v+1,v+m+1,cmp);

    int i=1;
    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++;
    }
    fout<<costmin<<"\n";
    fout<<n-1<<"\n";
    for(int i=0;i<n-1;i++)
    {
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
    }
}