using namespace std;
#include <fstream>
#include <vector>
ifstream fin("apm.in");
ofstream fout("apm.out");
#define Nmax 200001

int m, n, nr = 0;
int heap[Nmax], poz[Nmax], c[Nmax], pred[Nmax];
vector<bool> uz(Nmax);
vector< pair<int, int> > G[Nmax];

void read() ;
void push(int) ;
int get_min() ;

int main()
{
    int i, vf, s = 0;
    vector< pair<int, int> >::iterator it;
    
    read();
    push(1); uz[1] = 1;
    
    for(i = 1; i <= n; ++i)
    {
        vf = get_min(); uz[vf] = 1; s += c[vf];
        for(it = G[vf].begin(); it != G[vf].end(); ++it)
            if(!uz[it -> first])
                if(poz[it -> first] == 0 ||
                   c[it -> first] > (it -> second))
                   {
                       c[it -> first] = (it -> second);
                       pred[it -> first] = vf;
                       
                       push(it -> first);
                   }
    }
    
    fout << s << '\n' << n - 1 << '\n';
    
    for(i = 2; i <= n; ++i)
        fout << i << ' ' << pred[i] << '\n';
    return 0;
}

void read()
{
    int a, b, c;
    fin >> n >> m;
    
    for(int i = 1; i <= m; ++i)
    {
        fin >> a >> b >> c;
        G[a].push_back( make_pair(b, c) );
        G[b].push_back( make_pair(a, c) );
    }
}


void push(int vf)
{
    if(!poz[vf]) heap[++nr] = vf, poz[vf] = nr;
    
    int p = poz[vf];
    while(p > 1 && c[heap[p]] < c[heap[p / 2]])
    {
        swap(heap[p], heap[p / 2]);
        poz[heap[p]] = p;
        poz[heap[p / 2]] = p / 2;
        p >>= 1;
    }
}


int get_min()
{
    int p, rez = heap[1]; poz[heap[1]] = 0;
    heap[1] = heap[nr]; poz[heap[1]] = 1; heap[nr] = 0; --nr;
    
    for(p = 1; 2 * p <= nr;)
    {
        if(2 * p + 1 > nr)
        {
            if(c[heap[p]] > c[heap[2 * p]])
            {
                swap(heap[p], heap[2 * p]);
                poz[heap[p]] = p;
                poz[heap[2 * p]] = 2 * p;
            }
            return rez;
        }
        
        if(c[heap[2 * p]] < c[heap[2 * p + 1]])
        {
            if(c[heap[p]] > c[heap[2 * p]])
            {
                swap(heap[p], heap[2 * p]);
                poz[heap[p]] = p;
                poz[heap[2 * p]] = 2 * p;
                p = 2 * p;
            }
            else return rez;
        }
        else
        {
            if(c[heap[p]] > c[heap[2 * p + 1]])
            {
                swap(heap[p], heap[2 * p + 1]);
                poz[heap[p]] = p;
                poz[heap[2 * p]] = 2 * p + 1;
                p = 2 * p + 1;
            }
            else return rez;
        }
    }
    return rez;
}