#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
#include <bitset>
#define NMax 200000
using namespace std;
typedef struct
{
    int x,y,cost;
}NOD;
struct CMP
{
    bool operator()(const NOD A,const NOD B)
    {
        return (A.cost<B.cost)?false:true;
    }
};
std::vector< std::pair<int,int> > G[NMax],SUB;
std::vector< NOD > heaptest;
std::bitset<NMax> viz;
int n,m,x,y,cost;
void APM(int x0)
{
    viz[x0] = true;
    std::make_heap(heaptest.begin(),heaptest.end(),CMP());
    while(!heaptest.empty())
    {
        NOD aux = heaptest.front();
        std::pop_heap(heaptest.begin(),heaptest.end(),CMP());
        heaptest.pop_back();
        if(!viz[aux.x]||!viz[aux.y])
        {
            if(!viz[aux.x])
            {
                viz[aux.x] = true;
                for(int i=0;i<G[aux.x].size();++i)
                {
                    if(!viz[G[aux.x][i].first])
                    {
                        NOD aux2;
                        aux2.x = aux.x;
                        aux2.y = G[aux.x][i].first;
                        aux2.cost = G[aux.x][i].second;
                        heaptest.push_back(aux2);
                        std::push_heap(heaptest.begin(),heaptest.end(),CMP());
                    }
                }
            }
            else if(!viz[aux.y])
            {
                viz[aux.y] = true;
                for(int i=0;i<G[aux.y].size();++i)
                {
                    if(!viz[G[aux.y][i].first])
                    {
                        NOD aux2;
                        aux2.x = aux.y;
                        aux2.y = G[aux.y][i].first;
                        aux2.cost = G[aux.y][i].second;
                        heaptest.push_back(aux2);
                        std::push_heap(heaptest.begin(),heaptest.end(),CMP());
                    }
                }
            }
            cost += aux.cost;
            SUB.push_back( std::make_pair(aux.x,aux.y) );
            if(SUB.size()==n-1)break;
        }
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&cost);
        G[x].push_back( std::make_pair(y,cost) );
        G[y].push_back( std::make_pair(x,cost) );
    }
    for(int i=0;i<G[1].size();++i)
    {
        NOD aux;
        aux.x = 1;
        aux.y = G[1][i].first;
        aux.cost = G[1][i].second;
        heaptest.push_back(aux);
    }
    cost = 0;
    APM(1);
    printf("%d\n%d\n",cost,SUB.size());
    for(int i=0;i<SUB.size();++i)
    {
        printf("%d %d\n",SUB[i].first,SUB[i].second);
    }
    return 0;
}