#include <queue>
#include <fstream>

using namespace std;

struct edge
{
    int u, v, d;
};

struct edgeCmp
{
    int operator()(const edge& a, const edge &b){ return a.d > b.d; }
};

int find(vector<int> &C, int x)
{
    return x == C[x] ? x : find(C,C[x]);
}

void Kruskal(priority_queue <edge, vector<edge>, edgeCmp> &Q, int N)
{
    vector<edge> T;
    vector<int> C(N+1);
    vector<int> R(N+1,0);
    int weight = 0;
    for(int i = 0; i < N + 1;i++) C[i] = i;

    while( (int)T.size() < N-1 && !Q.empty() ) {
        edge e = Q.top();Q.pop();

        int uc = find(C,e.u), vc = find(C,e.v);
        if(uc != vc)
        {
            weight += e.d;
            T.push_back(e);
            if(R[uc] > R[vc]) C[vc] = uc;
            else if(R[vc] > R[uc]) C[uc] = vc;
            else { C[vc] = uc; R[uc]++; }
        }

    }
    ofstream fout("apm.out");
    fout<<weight<<"\n"<<T.size()<<"\n";
    for(int i = 0; i < (int) T.size();i++)
        fout<<T[i].v<<" "<<T[i].u<<"\n";
}

int main() {
    int N, M;
    ifstream fin("apm.in");
    fin>>N>>M;
    priority_queue <edge, vector<edge>, edgeCmp> Q;
    for(int i = 0;i< M;i++) {
        int n1,n2,cost;
        fin>>n1>>n2>>cost;
        edge e;
        e.u = n1;
        e.v = n2;
        e.d = cost;
        Q.push(e);
    }
    Kruskal(Q,N);

}