#include <fstream>
#include <vector>
#define nmax 200011
#define inf 200000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector < pair <int,int> > G[nmax],apm;
int poz,i,j,x,y,c,k,dim,v[nmax],vec[nmax],H[nmax],Poz[nmax],sol,rez,n,m,nod;
void apm_add(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<dim){
            int poz=2*k;
             if(poz+1<=dim&&v[H[poz]]>v[H[poz+1]])
            poz++;
        if(v[H[k]]>v[H[poz]])
        {
            swap(Poz[H[k]],Poz[H[poz]]);
            swap(H[k],H[poz]);
            k=poz;
        }
        else
            break;
    }
    }
void heap_add(int nod){
    H[++dim]=nod;
    Poz[nod]=dim;
    up(dim);
    }
int heap_extract()
{
    int x=H[1];
    swap(H[dim],H[1]);
    swap(Poz[H[dim]],Poz[H[1]]);
    dim--;
    down(1);
    Poz[x]=0;
    return x;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
            f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
    for(i=1;i<=n;i++)
        v[i]=inf;
    v[1]=0;
    apm_add(1);
    for(i=2;i<=n;i++)
        heap_add(i);
    for(i=1;i<n;i++)
    {
        x=heap_extract();
        apm_add(x);
        rez+=v[x];
        apm.push_back(make_pair(x,vec[x]));
        for(j=0;j<G[x].size();j++)
        {
            nod=G[x][j].first;
            if(Poz[nod])
                up(Poz[nod]);
        }
    }
 g<<rez<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;i++)
        g<<apm[i].first<<' '<<apm[i].second<<'\n';

    return 0;
}