#include <iostream>
#include<fstream>
#include<vector>
#define Nmax 200001
#define inf 1000000000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,heap_node[Nmax],i,j,m,x,y,cst,ct,parrent[Nmax];
vector<pair<int,int> >v[Nmax];
bool ok;
struct heap
{
    int nod,cost;
};
heap h[Nmax];
void up(int p)
{
    while(p>1 && h[p].cost<h[p/2].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p/2].nod]);
        swap(h[p],h[p/2]);
        p/=2;
    }
}
void down(int p)
{
    if((p<<1)<=n && (p<<1)+1<=n && h[p<<1].cost<h[(p<<1)+1].cost && h[p<<1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p<<1].nod]);
        swap(h[p],h[p<<1]);
        down(p<<1);
    }
    else
    if((p<<1)<=n && (p<<1)+1<=n && h[p<<1].cost>h[(p<<1)+1].cost && h[(p<<1)+1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[(p<<1)+1].nod]);
        swap(h[p],h[(p<<1)+1]);
        down((p<<1)+1);
    }
    else
    if((p<<1)<=n && h[p<<1].cost<h[p].cost)
    {
        swap(heap_node[h[p].nod],heap_node[h[p<<1].nod]);
        swap(h[p],h[p<<1]);
        down(p<<1);
    }
}
inline void cut(int k)
{
    swap(heap_node[h[k].nod],heap_node[h[n].nod]);
    swap(h[k],h[n]);
    n--;
    up(k);
    down(k);
}
inline void BuildHeap()
{
    for(int i=1;i<=n;i++)
        up(i);
}
inline int extractMin()
{
    return h[1].nod;
}
inline void Prim(int nod)
{
    int i,k,j,l,c;
    for(i=1;i<=n;i++)
    {
        h[i].nod=i;
        heap_node[i]=i;
        h[i].cost=inf;
    }
    h[nod].cost=0;
    BuildHeap();
    while(n>=1)
    {
        nod=extractMin();
        for(k=0;k<v[nod].size();k++)
            if(heap_node[v[nod][k].first] <= n)
        {
            j=heap_node[v[nod][k].first];
            c=v[nod][k].second;
            if(h[j].cost>c)
            {
                h[j].cost=c;
                parrent[h[j].nod]=nod;
                up(j);
            }
        }
        cut(heap_node[nod]);
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cst;
        v[x].push_back(make_pair(y,cst));
        v[y].push_back(make_pair(x,cst));
    }
    int n1=n;
    Prim(1);
    n=n1;
    for(i=2;i<=n;i++)
    {
        j=parrent[i];
        ok=1;
        for(int k=0;k<v[i].size() && ok;k++)
            if(v[i][k].first==j)
            {
                ct+=v[i][k].second;
                ok=0;
            }
    }
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=2;i<=n;i++)
        g<<i<<' '<<parrent[i]<<'\n';
}