#include <fstream>
#include <utility>
#include <vector>
#define NMAX 200005
#define INF 999999999

using namespace std;

FILE* f=freopen("apm.in","r",stdin);
FILE* o=freopen("apm.out","w",stdout);

typedef pair<int, int> pr;
int n,m;
int parent[NMAX];
int dist[NMAX], totCost;
int visited[NMAX];
int pozInHeap[NMAX];
vector<pr> graph[NMAX];
pr heap[NMAX]; int heapSize;

void HeapUpdatePosition(int child)
{
    int parent=child/2;
    pr aux=heap[child];
    while(parent>=1)
    {
        if(heap[parent].second>aux.second)
        {
            pozInHeap[heap[parent].first]=pozInHeap[heap[child].first];
            heap[child]=heap[parent];
            child=parent;
            parent=child/2;
        }
        else break;
    }
    heap[child]=aux;
    pozInHeap[aux.first]=child;
}

void HeapInsert(pr x)
{
    if(!pozInHeap[x.first]) {
        heapSize+=1;
        heap[heapSize]=x;
        pozInHeap[x.first]=heapSize;
        HeapUpdatePosition(heapSize);
    }
    else {
        heap[pozInHeap[x.first]]=x;
        HeapUpdatePosition(x.first);
    }
}

void HeapPop()
{
    swap(heap[1],heap[heapSize]);
    pozInHeap[heap[heapSize].first]=0;
    heapSize-=1;
    if(!heapSize) return;
    int parent=1;
    int child=parent*2;
    pr aux=heap[1];
    pozInHeap[heap[1].first]=1;
    while(child<=heapSize)
    {
        if(child!=heapSize)
            if(heap[child].second>heap[child+1].second)
                child=child+1;
        if(aux.second>heap[child].second)
        {
            pozInHeap[heap[child].first]=pozInHeap[heap[parent].first];
            heap[parent]=heap[child];
            parent=child;
            child=parent*2;
        }
        else break;
    }
    heap[parent]=aux;
    pozInHeap[aux.first]=parent;
}

void Prim(int x)
{
    for(int i=1;i<=n;++i)
    {
        parent[i]=x;
        dist[i]=INF;
    }

    parent[x]=dist[x]=0;
    HeapInsert(make_pair(x,0));
    while(heapSize)
    {
        int poz=heap[1].first;
        HeapPop();
        visited[poz]=1;
        for(int i=0;i<graph[poz].size();++i)
        {
            int ind=graph[poz][i].first;
            int c=graph[poz][i].second;
            if(dist[ind]>c&&!visited[ind])
            {
                dist[ind]=c;
                parent[ind]=poz;
                HeapInsert(graph[poz][i]);
            }
        }
    }

    for(int i=1;i<=n;++i) totCost+=dist[i];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        graph[x].push_back(make_pair(y,c));
        graph[y].push_back(make_pair(x,c));
    }

    Prim(1);

    printf("%d\n%d\n",totCost,n-1);
    for(int i=2;i<=n;++i)
        printf("%d %d\n",i,parent[i]);

    return 0;
}