#include <bits/stdc++.h>

using namespace std;

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

int nrNodes, nrEdges, father[200001],sizeTree[200001],x;
vector<tuple<int,int,int>> edges,mst;
tuple<int,int,int> emptyTuple;

void createSet(int node)
{
    father[node]=node;
    sizeTree[node]=1;
}

int findRoot(int node)
{
    if(father[node]!=node)
    {
        x=findRoot(father[node]);
        father[node]=x;
        return x;
    }
    else
        return node;
}

bool unite(int node1, int node2)
{
    int father1 = findRoot(node1), father2 = findRoot(node2);

    if(father1!=father2)
    {
        if(sizeTree[father1]>sizeTree[father2])
        {
            sizeTree[father1]+=sizeTree[father2];
            father[father2]=father1;
        }
        else
        {
            sizeTree[father2]+=sizeTree[father1];
            father[father1]=father2;
        }
        return 1;
    }
    return 0;
}

bool sortCondition(tuple<int,int,int>tupleRandom1,tuple<int,int,int>tupleRandom2)
{
    return get<2>(tupleRandom1)<get<2>(tupleRandom2);
}

int main()
{
    f>>nrNodes>>nrEdges;
    int node1,node2,weight;
    tuple<int,int,int> tupleaux;

    for(int i=1;i<=nrNodes;i++)
        createSet(i);

    for(int i=1; i<=nrEdges; i++)
    {
        f>>node1>>node2>>weight;
        tupleaux = make_tuple(node1,node2,weight);
        edges.push_back(tupleaux);
    }
    sort(edges.begin(),edges.end(), sortCondition);

    for(int i=0; i<edges.size(); i++)
        if(unite(get<0>(edges[i]),get<1>(edges[i]))==1)
            mst.push_back(edges[i]);
    int s=0;
    for(int i=0; i<mst.size();i++)
        s+=get<2>(mst[i]);
    g<<s<<'\n';
    g<<mst.size()<<'\n';
    for(int i=0; i<mst.size();i++)
        g<<get<0>(mst[i])<<" "<<get<1>(mst[i])<<'\n';
    return 0;
}