#include <fstream>
#include <vector>
#include <algorithm>
#include <set>

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

void prim();

struct muchie
{
  int a, b, c;
  bool operator <(const muchie& other) const
  {
    if(c==other.c)
    {
      if(a==other.a) return(b<other.b);
      return (a<other.a);
    }
    return c<other.c;
  }
};

set <muchie> s;
vector< muchie > v[200005], m;

int n, nrm, p[200005], cost;
bool f[200005];

int main()
{
    int i, a, b, c;
    fin>>n>>nrm;
    for(i=1; i<=nrm; i++)
    {
        fin>>a>>b>>c;
        v[a].push_back({a, b, c});
        v[b].push_back({b, a, c});
    }
    prim();
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(auto k:m) fout<<k.a<<' '<<k.b<<'\n';
    return 0;
}

void prim()
{
    muchie mch;
    f[1]=true;
    for(auto i:v[1])
    {
        s.insert(i);
    }
    while(s.size() && m.size()<(n-1))
    {
        mch=*(s.begin());
        s.erase(s.begin());
        if(f[mch.b]==false)
        {
            cost+=mch.c;
            m.push_back(mch);
            f[mch.b]=true;
            for(auto i:v[mch.b])
            {
                if(f[i.b]==false) s.insert(i);
            }
        }
    }
}