//DOPAJUL CONTINUA
//ALGORITMUL LUI PRIM WOO
#include<stdio.h>
#include<climits>
#include<algorithm>
#include<vector>
#define MAXV 200000
#define MAXE 400000
#define INF INT_MAX
struct HipHipHooray
{
    int vertex,cost;
};
struct Edge
{
    int src,dst,cost;
};
//FUNCTII MULTE DE HEAPURI
int left_son(int nod);
int right_son(int nod);
int father(int nod);
void add(int vertex,int cost);
void rmv(int nod);
void sift(int nod);
void percolate(int nod);
void swap_nodes(int nod1,int nod2);
void init();
FILE*fin,*fout;
HipHipHooray heap[MAXV+1];
int pos[MAXV+1];
int e[MAXV+1];
bool in_heap[MAXV+1];
Edge edges[MAXE+1];
int sol[MAXE+1];
std::vector<int> neighbors[MAXV+1];
int N=0;
int E,V;
int main()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    fscanf(fin,"%d%d",&V,&E);
    for(int i=1;i<=E;i++)
    {
        fscanf(fin,"%d%d%d",&edges[i].src,&edges[i].dst,&edges[i].cost);
        neighbors[edges[i].src].push_back(i);
        neighbors[edges[i].dst].push_back(i);
    }
    init();
    int nrsol=0;
    int totalCost=0;
    while(N>0)
    {
        int v=heap[1].vertex;
        rmv(1);
        if(e[v]!=0)
        {
            sol[++nrsol]=e[v];
            totalCost+=edges[e[v]].cost;
        }
        for(unsigned int i=0;i<neighbors[v].size();i++)
        {
            int muchie=neighbors[v][i];
            int vec=edges[muchie].src;
            if(v==vec)
            {
                vec=edges[muchie].dst;
            }
            if(in_heap[vec] && heap[pos[vec]].cost>edges[muchie].cost)
            {
                heap[pos[vec]].cost=edges[muchie].cost;
                e[vec]=muchie;
                percolate(pos[vec]);
            }
        }
    }
    fprintf(fout,"%d\n%d\n",totalCost,nrsol);
    for(int i=1;i<=nrsol;i++)
    {
        fprintf(fout,"%d %d\n",edges[sol[i]].src,edges[sol[i]].dst);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}
int left_son(int nod)
{
    return 2*nod;
}
int right_son(int nod)
{
    return 2*nod+1;
}
int father(int nod)
{
    return nod/2;
}
void add(int vertex,int cost)
{
    heap[++N].vertex=vertex;
    heap[N].cost=cost;
    pos[vertex]=N;
    in_heap[vertex]=1;
    percolate(N);
}
void rmv(int nod)
{
    in_heap[heap[nod].vertex]=0;
    swap_nodes(nod,N);
    N--;
    if(nod>1 && heap[nod].cost<heap[father(nod)].cost)
    {
        percolate(nod);
    }
    else
    {
        sift(nod);
    }
}
void sift(int nod)
{
    int son;
    do
    {
        son=0;
        if(right_son(nod)<=N)
        {
            if(heap[left_son(nod)].cost<heap[right_son(nod)].cost)
            {
                son=left_son(nod);
            }
            else
            {
                son=right_son(nod);
            }
        }
        else if(left_son(nod)<=N)
        {
            son=left_son(nod);
        }
        if(heap[nod].cost<heap[son].cost)
        {
            son=0;
        }
        if(son)
        {
            swap_nodes(nod,son);
            nod=son;
        }
    }while(son);
}
void percolate(int nod)
{
    while(nod>1 && heap[nod].cost<heap[father(nod)].cost)
    {
        swap_nodes(nod,father(nod));
        nod=father(nod);
    }
}
void swap_nodes(int nod1,int nod2)
{
    std::swap(heap[nod1].vertex,heap[nod2].vertex);
    std::swap(heap[nod1].cost,heap[nod2].cost);
    std::swap(pos[heap[nod1].vertex],pos[heap[nod2].vertex]);
}
void init()
{
    for(int i=1;i<=V;i++)
    {
        add(i,INF);
    }
}