#include<fstream>
#include<algorithm>
#include<vector>
#define nmax 200003
#define mmax 400003

using namespace std;

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

int n,m;
int totalW;

struct edge
{
    int vertex1;
    int vertex2;
    short int weight;
};

edge e[mmax];

int mst[nmax];

int father[nmax];
int nRank[nmax];


int compF(struct edge e1, struct edge e2)
{
    return e1.weight <= e2.weight;
}

bool connected(int v1, int v2)
{
    while(father[v1] != 0)
        v1 = father[v1];

    while(father[v2] != 0)
        v2 = father[v2];

    return (v1 == v2);
}

void join(int v1, int v2)
{
    while(father[v1] != 0)
        v1 = father[v1];

    while(father[v2] != 0)
        v2 = father[v2];

    if(nRank[v1] > nRank[v2])
    {
        father[v2] = v1;
    }
    else if(nRank[v2] > nRank[v1])
    {
        father[v1] = v2;
    }
    else
    {
        father[v2] = v1;
        nRank[v1]++;
    }
}



void kruskal()
{
    int p = 0;

    for(int i=1; i<n; i++)
    {
        while(connected(e[p].vertex1, e[p].vertex2))
            p++;

        join(e[p].vertex1, e[p].vertex2);
        totalW = totalW + e[p].weight;
        mst[i] = p;
    }

    out<<totalW<<'\n'<<n-1<<'\n';

    for(int i = 1; i < n; i++)
        out<<e[mst[i]].vertex1<<" "<<e[mst[i]].vertex2<<'\n';

}



int main()
{
    in>>n>>m;

    for(int i=0; i<m; i++)
    {
        in>>e[i].vertex1>>e[i].vertex2>>e[i].weight;
    }

    in.close();

    sort(e, e+m, compF);

    for(int i=1; i<=n; i++)
    {
        nRank[i] = 1;
    }

    kruskal();

    out.close();

    return 0;

}