#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#include<queue>

//cu Prim (cea din 6 sept 2018 e cu Kruskal)

using namespace std;


#define INF 0x3f3f3f3f
#define NMAX 200005



bool viz[NMAX];
int T[NMAX];



int main(){

FILE * in = fopen("apm.in","r"), *out = fopen("apm.out", "w");
int n, m, x, y, c, cMin = 0;
priority_queue < pair<int, int>, vector< pair<int,int> >, greater< pair<int,int> > > pq;

fscanf(in,"%i %i", &n, &m);

int costMin[n+5];
vector < pair <int, int> > adj[n+5];



while( m-- ){

     fscanf(in,"%i %i %i", &x, &y, &c);

     adj[x].push_back( make_pair(y,c) );

     adj[y].push_back( make_pair(x,c) );

}



pq.push(make_pair(0,1));

memset(costMin,INF, sizeof(costMin));



while(!pq.empty()){

    while (viz[pq.top().second]) pq.pop();

    if(pq.empty()) continue;

    int x = pq.top().second;  

    cMin += pq.top().first;

    pq.pop();

    viz[x] = true;

    

    for(size_t i = 0; i<adj[x].size();i++){

       y=adj[x][i].first; 

       c=adj[x][i].second;

       if( !viz[y] && costMin[y] > c){

          costMin[y] = c; T[y] = x;

          pq.push(make_pair(c,y));

       }

    }

}



fprintf(out,"%i\n%i\n", cMin, n-1);

for(int i=2; i<=n; i++)

       fprintf(out,"%i %i \n", T[i], i);



fclose(in); fclose(out);

return 0;

}