#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

FILE *in = fopen("apm.in","r"), *out = fopen("apm.out","w");

vector< vector< pair<int,int> > >graph;//grapminHeap[origine]=={destinatie,distanta_muchie}
vector<int>apm;//apm[fiu]==tata
vector<int>minHeap;//noduri
vector<int>dist;//dist[nod]==distanta pana acolo
vector<bool>connected;
int m, n, tot, heapCardinal;


void swap(int x, int y)
{
    int t = minHeap[x];
    minHeap[x] = minHeap[y];
    minHeap[y] = t;
}

void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( dist[ minHeap[tata] ] > dist[ minHeap[what] ] )
        {

            swap(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void downheap(int what)
{
    int f;
    while ( what <= heapCardinal )
    {
        f = what;
        if ( (what<<1) <= heapCardinal )
        {
            f = what << 1;
            if ( f + 1 <= heapCardinal )
                if ( dist[ minHeap[f + 1] ] < dist[ minHeap[f] ] )
                    ++f;
        }
        else
            return;

        if ( dist[ minHeap[what] ] > dist[ minHeap[f] ] )
        {
            swap(what, f);

            what = f;
        }
        else
            return;
    }
}

void prim(){

minHeap.resize(n+1);

minHeap[++heapCardinal] = 1;

dist.resize(n+1,1 << 30);

dist[1] = 0;

connected.resize(n+1,false);

unsigned int i,j;
int tempDist;
int curr;

for( i = 2; i <= n; i ++ )
{
    minHeap[++heapCardinal] = i;
    upheap( heapCardinal );
}

while( heapCardinal )
{
    //scoatem primul element din heap
    curr = minHeap[1];
    connected[curr] = true;
    for( i = 0; i < graph[curr].size(); i ++ )//parcurgem nodurile adiacente celui curent;
    {
                tempDist = graph[curr][i].second;//salvam distanta din nodul curent in cel adiacent
                if ( tempDist < dist[ graph[curr][i].first ] )//distanta calculata din nodul curent este mai mica decat cea calculata anterior
                {
                    dist[ graph[curr][i].first ] = tempDist;
                    upheap(graph[curr][i].first);
                 if(!connected[graph[curr][i].first])
                    apm[ graph[curr][i].first ] = curr;
                }
    }
    tot+=dist[ curr ];
    swap(1, heapCardinal);
    --heapCardinal;
    //refacem heap-ul
    downheap(1);

    for( i = heapCardinal/2; i >= 1; i -- )
        downheap(i);
}

}


int main()
{
int x, y, z, i;
fscanf(in, "%d %d", &n, &m);
graph.resize(n+1);
apm.resize(n+1);

for( i = 0; i < m; i ++ )
    {fscanf(in, "%d %d %d", &x, &y, &z);
    graph[x].push_back( make_pair(y,z) );
    graph[y].push_back( make_pair(x,z) );
    }

prim();
fprintf(out,"%d",tot);
fprintf(out,"\n");
fprintf(out,"%d",n-1);
fprintf(out,"\n");

for( i = 2; i <= n; i ++ )
    {fprintf( out, "%d %d", i, apm[i] );
    fprintf(out, "\n");
    }

return 0;
}