#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));


for(int nr=1; nr<=n; nr++){

    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;

}