#include <iostream>

#include <vector>
#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<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

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;

unsigned int i;
int tempDist;
int curr;

while( heapCardinal )
{
    //scoatem primul element din heap
    curr = minHeap[1];
    swap(1, heapCardinal);
    poz[ minHeap[1] ] = 1;
    --heapCardinal;
    //refacem heap-ul
    downheap(1);
    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 ( poz[ graph[curr][i].first ] != -1 )
                upheap( poz[ graph[curr][i].first ] );
            else
            {
                minHeap[++heapCardinal] = graph[curr][i].first ;
                poz[ minHeap[heapCardinal] ] = heapCardinal;
                upheap( heapCardinal );
            }
            apm[ graph[curr][i].first ] = curr;

        }
    }
    tot+=dist[ curr ];
}

}


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;
}