#include <fstream>
#include <vector>
#include <algorithm>
const int NMAX=200005;

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

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

vector< muchie > mc, ans;
int t[NMAX];
int n, m;

int find(int);
bool un(int, int);
void kruskal();

int main()
{
    int i, a, b, c;
    fin>>n>>m;
    for(i=1; i<=n; i++) t[i]=i;
    for(i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        mc.push_back({a, b, c});
    }
    kruskal();
    return 0;
}

void kruskal()
{
    int cnt=n, cost=0, i=0;
    sort(mc.begin(), mc.end());
    while(cnt>1 && i<m)
    {
        if(un(mc[i].a, mc[i].b))
        {
            cnt--;
            cost+=mc[i].c;
            ans.push_back(mc[i]);
        }
        i++;
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(auto j:ans) fout<<j.a<<' '<<j.b<<'\n';
}

int find(int nod)
{
    if(t[nod]==nod) return nod;
    t[nod]=find(t[nod]);
    return t[nod];
}

bool un(int a, int b)
{
    int ta=find(a);
    int tb=find(b);
    if(ta==tb) return false;
    if(ta<tb) t[tb]=ta;
    else t[ta]=tb;
    return true;
}