#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector< vector< pair<int,int> > >graph;//graph[origine]=={destinatie,distanta_muchie}
vector<int>apm;//apm[fiu]==tata
vector<int>minHeap;//nod,distanta_pana_acolo
vector<int>dist;
int m, n, tot;

bool comp( const int&x, const int&y ){
if(dist[x]>dist[y])
    return true;
return false;
}


void prim(){
make_heap( minHeap.begin(), minHeap.end(), comp );
unsigned int i,j;
int tempDist;
int curr;
while(!minHeap.empty())
    {
    curr = minHeap.front();
    for( j = 0; j < minHeap.size(); j ++ )//parcurgem nodurile din minHeap
        {
        for( i = 0; i < graph[minHeap[j]].size(); i ++ )
            {if( graph[ minHeap[j] ][i].first == curr )//nodul din minHeap il are in lista de adiacenta pe cel curent
                {
                tempDist = graph[ minHeap[j] ][i].second;//salvam distanta din nodul adiacent in cel curent
                if ( tempDist < dist[ minHeap[j] ] )//distanta calculata din nodul curent este mai mica decat cea calculata anterior
                    {dist[ minHeap[j] ] = tempDist;
                    apm[ minHeap[j] ] = curr;
                    //g<<"prin "<<curr+1<<" se ajunge mai repede in->"<<minHeap[j]+1<<"\n";
                    }
                break;
                }
            }

        }
    tot+=dist[ curr ];
    pop_heap( minHeap.begin(), minHeap.end(), comp );
    minHeap.pop_back();
    make_heap( minHeap.begin(), minHeap.end(), comp );
    }

}


int main()
{
int x, y, z, i;
f >> n >> m;
graph.resize(n);
apm.resize(n,-2);
minHeap.resize(n);
for( i = 0; i < n; i ++ )
    {minHeap[i] = i;
    }
dist.resize(n,1 << 30);
dist[0]=0;
for( i = 0; i < m; i ++ )
    {f >> x >> y >> z;
    x --;
    y --;
    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 = 1; i < n; i ++ )
    {
    g<<i+1<<" "<<apm[i]+1<<"\n";

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