#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< pair<int,int> >minHeap;//nod,distanta_pana_acolo
int m, n, tot;
struct vertex{
 int nod,cost;
 vertex* next;
};
bool comp( const pair<int,int>&x, const pair<int,int>&y ){
if(x.second>y.second)
    return true;
return false;
}

void prim(){
make_heap( minHeap.begin(), minHeap.end(), comp );
int i,j,tempDist;
pair<int,int> curr;
while(!minHeap.empty())
    {
    curr = minHeap.front();
    for( i = 0; i < graph[curr.first].size(); i ++ )//parcurgem nodurile adiacente celui curent;
        {
        for( j = 0; j < minHeap.size(); j ++ )//parcurgem nodurile din minHeap
            {
            if( minHeap[j].first == graph[curr.first][i].first )//nodul adiacent este in minHeap
                {                                               //deci nu e in apm
                tempDist = graph[curr.first][i].second;//salvam distanta din nodul curent in cel adiacent
                if ( tempDist < minHeap[j].second )//distanta calculata din nodul curent este mai mica decat
                    {minHeap[j].second = tempDist;  //cea calculata anterior
                    apm[ minHeap[j].first ] = curr.first;

                    }
                break;
                }
            }
        }
    tot+=curr.second;
    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 = 1; i < n; i ++ )
    {minHeap[i] = make_pair(i, 1 << 30);
    }
minHeap[0] = make_pair(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;
}