#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 up(int k)
{
    while(k/2)
    {
        if(v[H[k/2]] > v[H[k]])
        {
            swap(poz[H[k/2]],poz[H[k]]);
            swap(H[k/2],H[k]);
            k/=2;
        }
        else
            break;
    }
}
void down(int k)
{
    while(2*k<=hdim)
    {
        int po=2*k;
        if(po+1<=hdim && v[H[po]] > v[H[po+1]])
            po++;
        if(v[H[k]] > v[H[po]])
        {
            swap(poz[H[k]],poz[H[po]]);
            swap(H[k],H[po]);
            k=po;
        }
        else
            break;
    }
}
void heap_insert(int nod)
{
    H[++hdim]=nod;
    poz[nod]=hdim;
    up(hdim);
}
int heap_extract()
{
    int x=H[1];
    swap(H[1],H[hdim]);
    swap(poz[H[1]],poz[H[hdim]]);
    hdim--;
    down(1);
    poz[x]=0;
    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++)
    {
        heap_insert(i);
    }
    for(i=1;i<n;i++)
    {
        x=heap_extract();
        sol += v[x];
        apm_insert(x);
        apm.pb(mkp(x,vec[x]));
        for(j=0;j<G[x].size();j++)
        {
            nod=G[x][j].first;
            if(poz[nod])
                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;
}