#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#define infinit INT32_MAX

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
typedef pair<int,pair<int,int>> muchie;

vector<vector<pair<int,int>>> la;
int cost;

void Prim(int s, int n,  vector<pair<int,int>> &muchii_apcm){
    int u,i,v,j;
	vector<int> tata(n+1,0),viz(n+1,0),d(n+1,infinit);
	int w_uv;



	//	set <muchie_min_varf, comparator_muchie_min_varf> Q;
	priority_queue<muchie,vector<muchie>,greater<muchie>> Q;
	viz[s]=1;
	for(auto &x:la[s])
        Q.push({x.second,{s,x.first}}); //suficient sa inseram in Q doar varful de start, nu toate varfurile, pentru ca nu facem actualizarea etichetei, ci stergere+reinserare
	//for(i=1;i<=n-1;i++){
    while(Q.size()>0)
{

         muchie z;
         u=0;
		do { z=Q.top();Q.pop();

		u=z.second.first;
		v=z.second.second;

		}
		while ((Q.size()>0 && viz[u] && viz[v]));
		if(Q.size()==0 && viz[u] && viz[v]) break;

        if (viz[u]==1){
            swap(u,v);
        }

		viz[u]=1;
		muchii_apcm.push_back({u,v});

        cost+=z.first;

		for(auto &p:la[u]  ){
			v=p.first;
			w_uv=p.second;

			if(viz[v]==0) {
 	            Q.push({w_uv,{u,v}});

			}
		}

	}
	cout<<cost;
}
int main(){

	int m,n, x,y,c,i,j,s,mc;

	f>>n;
	f>>m;

     la.resize(n+1);

	for(i=1;i<=m;i++){
		f>>x>>y>>c;
		la[x].push_back(make_pair(y,c));
		la[y].push_back(make_pair(x,c));
	}
	f.close();

    vector<pair<int,int>> muchii_apcm;

    Prim(1,n, muchii_apcm);


    g<<cost<<"\n"<<n-1<<"\n";
   	for(auto &p:muchii_apcm){
			g<<p.first<<" "<<p.second<<"\n";

    	}
    g.close();

	return 0;

}