#include <bits/stdc++.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct afis{int x;int y;}af[1002];
struct edges{int x;int y;int w;}v[1003];
bool m[1003][1003];
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[1003];
    cpy(vap,vp);
    for(int l=1;l<=n;l++)
        if(m[l][nd]==1 && l!=lastnd)
        {
            if(vap[l]==1)
            {
                ec=1;
                return;
            }
            else
            {
                vp[l]=1;
                dfs(l,vp,ec,nd);
                if(ec==1)return;
            }
        }
}
bool cycle(int nd)
{
    bool vap[1003]={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;
        m[x][y]=m[y][x]=1;
        if(cycle(x)==1)
        {
            m[x][y]=m[y][x]=0;
        }
        else {s+=w;howm++;af[howm].x=x;af[howm].y=y;}
        i++;
    }
    g<<s<<'\n'<<n-1<<'\n';
    for(i=1;i<n;i++)
        g<<af[i].x<<" "<<af[i].y<<'\n';
}