#include <fstream>
#include <vector>

#define NDIM 200005
#define pb push_back
#define mkp make_pair
#define inf 200000200
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int i,j,nod,n,m,a,b,c,x,v[NDIM],poz[NDIM],H[2*NDIM],hdim,vec[NDIM],sol;
vector < pair <int,int> > G[NDIM],apm;
void apm_insert(int x)
{
    for(int i=0;i<G[x].size();i++)
    {
        int nod = G[x][i].first;
        int cost = G[x][i].second;
        v[nod]=min(v[nod],cost);
        if(v[nod]==cost)
            vec[nod]=x;
    }
}
void H_up(int po)
{
    int tata =po/2;
    while(v[H[tata]] > v[H[po]] && tata >= 1)
    {
        swap(H[tata],H[po]);
        swap(poz[H[tata]],poz[H[po]]);
        tata/=2;po/=2;
    }
}
void H_down(int po)
{
    int fiu = 2*po;
    while(fiu <= hdim)
    {
        if(fiu+1 <= hdim && v[H[fiu]] > v[H[fiu+1]])
            fiu++;
        if(v[H[fiu]] < v[H[po]])
        {
            swap(H[fiu],H[po]);
            swap(poz[H[fiu]],poz[H[po]]);
            po = fiu;
            fiu = 2*po;
        }
        else
            break;
    }
}
void H_insert(int x)
{
    H[++hdim] = x;
    poz[x] = hdim;
    H_up(hdim);
}
int H_extract()
{
    int x = H[1];
    poz[H[1]] = 0;
    H[1] = H[hdim];
    poz[H[1]] = 1;
    hdim--;
    return x;

}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>a>>b>>c;
        G[a].pb(mkp(b,c));
        G[b].pb(mkp(a,c));
    }
    for(i=1;i<=n;i++)
        v[i]=inf;
    v[1]=0;
    apm_insert(1);
    for(i=2;i<=n;i++)
    {
        H_insert(i);
    }
    for(i=1;i<n;i++)
    {
        x=H_extract();
        apm_insert(x);
        sol += v[x];
        apm.pb(mkp(x,vec[x]));
        for(j=0;j<G[x].size();j++)
        {
            nod=G[x][j].first;
            if(poz[nod])
                H_up(poz[nod]);
        }
    }
    fout<<sol<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        fout<<apm[i].first<<' '<<apm[i].second<<'\n';
    return 0;
}