#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{
    int x, y;
    int cost;
    int viz = 0;
    int i;
}muc[200001];

struct compare{
  public:
  bool operator()(muchie& a,muchie& b) // overloading both operators
  {
      return a.cost > b.cost; // if you want increasing order;(i.e increasing for minPQ)
   }
};

int n, m;
int viz[200001];
priority_queue<muchie, vector<muchie>, compare> q;

void citire()
{
    fin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        fin >> muc[i].x >> muc[i].y >> muc[i].cost;
        muc[i].i = i;
    }

}

void adaugare_muchii(int start)
{
    for(int i = 0; i < m; ++i)
        if(!muc[i].viz && (muc[i].x == start || muc[i].y == start))
        {
            q.push(muc[i]);
        }

}

int prim()
{
    int c = 0;
    adaugare_muchii(1);
    viz[1] = 1;
    while(!q.empty())
    {
        muchie el = q.top();
        q.pop();
        if((viz[el.x] ^ viz[el.y]) == 1)
        {
            c += el.cost;
            muc[el.i].viz = 1;
            if(!viz[el.x])
            {
                viz[el.x] = 1;
                adaugare_muchii(el.x);
            }
            else
            {
                viz[el.y] = 1;
                adaugare_muchii(el.y);
            }
        }
    }

    return c;
}

void afisare()
{
    for(int i = 0; i < m; ++i)
        if(muc[i].viz)
            fout << muc[i].x << ' ' << muc[i].y << '\n';
}

int main()
{
    citire();
//    while(!q.empty())
//    {
//        cout << q.top().x << ' ' << q.top().y << ' ' << q.top().cost << '\n';
//        q.pop();
//    }
    fout << prim() << '\n' << n - 1 << '\n';
    afisare();
    return 0;
}