#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< vector< pair<int,int> > >graph;//grapminHeap[origine]=={destinatie,distanta_muchie}
vector< vector< pair<int,int> > >apmgr;//grapminHeap[origine]=={destinatie,distanta_muchie}
vector<int>apm;//apm[fiu]==tata
vector<int>minHeap;//noduri
vector<int>dist;//dist[nod]==distanta pana acolo
//vector<int>poz;//poz[nod]==pozitia in minHeap
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] ] )
        {
            /*poz[ minHeap[what] ] = tata;
            poz[ minHeap[tata] ] = 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] ] )
        {
            /*poz[ minHeap[what] ] = f;
            poz[ minHeap[f] ] = what;**/

            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;

/*poz.resize(n+1, -1);

poz[1] = 1;*/

connected.resize(n+1,false);

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

for( i = 2; i <= n; i ++ )
{
    minHeap[++heapCardinal] = i;
    //poz[ minHeap[heapCardinal] ] = heapCardinal;
    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;
                 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 = 1; i <= heapCardinal; i ++ )
        upheap(i);
}

}


int main()
{
int x, y, z, i;
f >> n >> m;
graph.resize(n+1);
apm.resize(n+1,-2);

for( i = 0; i < m; i ++ )
    {f >> x >> y >> z;
    graph[x].push_back( make_pair(y,z) );
    graph[y].push_back( make_pair(x,z) );
    }

prim();
g<<tot<<"\n";
g<<n-1<<"\n";

for( i = 2; i <= n; i ++ )
    {g<<i<<" "<<apm[i]<<"\n";
    }

f.close();
g.close();
return 0;
}