#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct afis{int x;int y;}af[200002];
struct edges{int x;int y;int w;}v[400003];
struct nodes{vector <int> n,w;}ndd[200003];
int n,nre,x,y,w,i;
int howm=0;
bool srt(edges x,edges y)
{
    if(x.w>y.w)return 0;
    else if(x.w==y.w)
    {
        if(x.y>y.y)return 0;
        else if(x.y==y.y)
        {
            return x.x<y.x;
        }
        return 1;
    }
    return 1;
}
void cpy(bool from[],bool to[])
{
    for(int ii=1;ii<=n;ii++)
        to[ii]=from[ii];
}
void dfs(int nd,bool vap[],bool &ec,int lastnd)
{
    bool vp[200003];
    cpy(vap,vp);
    for(int l=0;l<ndd[nd].n.size();l++)
        if(ndd[nd].n[l]!=lastnd)
        {
            int ll=ndd[nd].n[l];
            if(vap[ll]==1)
            {
                ec=1;
                return;
            }
            else
            {
                vp[ll]=1;
                dfs(ll,vp,ec,nd);
                if(ec==1)return;
            }
        }
}
bool cycle(int nd)
{
    bool vap[200003]={0};
    bool ec=0;
    dfs(nd,vap,ec,0);
    return ec;
}
int main()
{
    f>>n>>nre;
    for(i=1;i<=nre;i++)
    {
        f>>x>>y>>w;
        v[i].x=x;
        v[i].y=y;
        v[i].w=w;
    }
    sort(v+1,v+nre+1,srt);
    i=1;
    int s=0;
    while(i<=nre && howm<n-1)
    {
        x=v[i].x;y=v[i].y;w=v[i].w;
        ndd[x].n.push_back(y);
        ndd[x].w.push_back(w);

        ndd[y].n.push_back(x);
        ndd[y].w.push_back(w);

        if(cycle(x)==1)
        {
            ndd[x].n.pop_back();
            ndd[x].w.pop_back();

            ndd[y].n.pop_back();
            ndd[y].w.pop_back();
        }
        else
        {
            s+=w;
            howm++;
            af[howm].x=x;
            af[howm].y=y;
            ndd[x].n.push_back(y);
            ndd[x].w.push_back(w);

            ndd[y].n.push_back(x);
            ndd[y].w.push_back(w);
        }
        i++;
    }
    g<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        g<<af[i].x<<" "<<af[i].y<<'\n';
}