#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;

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

edge e[mmax];

vector<int>mst;

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


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

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

    while(father[v2] != -1)
        v2 = father[v2];

    return (v1 == v2);
}

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

    while(father[v2] != -1)
        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()
{
    sort(e, e+m, compF);

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

    int totalW = 0;
    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.push_back(p);
    }

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

    vector<int>::iterator it;

    for(it = mst.begin(); it < mst.end(); it++)
        out<<e[*it].vertex1<<" "<<e[*it].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();

    kruskal();

    out.close();

    return 0;

}