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

using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");
const int nmax=2e5, mmax=4e5;
int n, m, cosmin;
int tata[nmax+5];
vector <pair <int, int> > APM;

struct muchie
{
    int x, y, c;
} G[mmax+5];


void citire(void)
{
    fi>>n>>m;
    for(int i=1; i<=m; i++)
        fi>>G[i].x>>G[i].y>>G[i].c;
}

int cmp(muchie a, muchie b)
{
    return a.c<b.c;
}

int find_set(int x)
{
    if(x==tata[x])
        return x;
    int r=find_set(tata[x]);
    tata[x]=r;
    return r;
}

void afisare(void)
{
    fo<<cosmin<<"\n"<<n-1<<"\n";
    for(auto edge:APM)
        fo<<edge.first<<" "<<edge.second<<"\n";
}

int main()
{
    citire();

    sort(G+1, G+m+1, cmp);

    for(int i=1; i<=n; i++)
        tata[i]=i;

    for(int i=1; i<=m; i++)
    {
        int rx=find_set(G[i].x);
        int ry=find_set(G[i].y);
        if(rx!=ry)
        {
            cosmin+=G[i].c;
            APM.push_back({G[i].x, G[i].y});
            tata[ry]=rx;
        }
    }

    afisare();

    fi.close();
    fo.close();
    return 0;
}