#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
int costFinal;
const int NMAX = 200010;
int id[NMAX];
int sz[NMAX];
vector<int> selectedEdges;
struct edge
{
    int start;
    int finish;
    int cost;
};
int findd(int p)
{
    int root = p;
    while(root!=id[root])
        root=id[root];
    while(p!=root)
    {
        int next=id[p];
        id[p]=root;
        p=next;
    }
    return root;
}
void unionn(int idx,int p,int q,int costx)
{
    int root1 = findd(p);
    int root2 = findd(q);
    if(root1==root2)
        return;
    costFinal+=costx;
    selectedEdges.push_back(idx);
    if(sz[root1]>sz[root2])
    {
        sz[root1]+=sz[root2];
        id[root2]=root1;
    }
    else
    {
        sz[root2]+=sz[root1];
        id[root1]=root2;
    }
}
bool compare(edge a,edge b)
{
    if(a.cost<b.cost)
        return true;
    return false;
}
vector<edge> edges;
int main()
{
    fin>>n>>m;
    for(int i = 0;i<=n;i++)
        id[i]=i,sz[i]=1;
    while(m--)
    {
        int x,y,c;
        fin>>x>>y>>c;
        edges.push_back({x,y,c});
    }
    sort(edges.begin(),edges.end(),compare);
    for(int i =0;i<edges.size();i++)
    {
        unionn(i,edges[i].start,edges[i].finish,edges[i].cost);
    }
    fout<<costFinal<<'\n';
    fout<<selectedEdges.size()<<'\n';
    for(int i = 0;i<selectedEdges.size();i++)
    {
        int id = selectedEdges[i];
        fout<<edges[id].finish<<" "<<edges[id].start<<'\n';
    }
    return 0;
}