#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxm 400002
#define maxn 200002
#define cc first
#define xx second.first
#define yy second.second
#define pb push_back
#define mkp make_pair
#define fr for

using namespace std;


int n,m,i,x,y,cst,nr,ver[maxn],zcst;

vector <pair<int,pair<int,int> > > vmu;
vector <pair<int,int> > vans ;
vector <int> lst[maxn];
vector <int> lcrt[maxn];

void dfs(int nd)
{
    if (ver[nd]) return;
    ver[nd]=1;
    for(int i=0;i<lcrt[nd].size();++i)
    {
        dfs(lcrt[nd][i]);
    }
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf ("%d%d",&n,&m);

    for (i=0; i<m; ++i)
    {
        scanf ("%d%d%d",&x,&y,&cst);
        lst[x].pb(y);
        lst[y].pb(x);
        vmu.pb(mkp(cst,mkp(x,y)));
    }
    //nr=n
    sort (vmu.begin(),vmu.end());
    nr=n;
    for (i=0; i<m; ++i)
    {
        cst=vmu[i].cc;
        x=vmu[i].xx;
        y=vmu[i].yy;

        memset(ver,0,sizeof(ver));
        dfs(y);
        if (!ver[x])
        {
            --nr;
            lcrt[y].pb(x);
            lcrt[x].pb(y);
            zcst+=cst;
            vans.pb(mkp(y,x));
        }
        else
        {
            int kk=1;
        }
        if (nr==1)
        {
            break;
        }
    }
    printf("%d\n",zcst);
    printf("%d\n",n-1);

    for (i=0;i<n-1;++i)
    {
        printf("%d %d\n",vans[i].first,vans[i].second);
    }

    return 0;
}