#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#define infinit INT32_MAX
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");


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;

	d[s]=0;

	//	set <muchie_min_varf, comparator_muchie_min_varf> Q;
	set<pair<int,int>> Q;
	Q.insert({d[s],s}); //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++){

		//u=(*Q.begin()).second;//varful nevizitat cu d minim
		auto z=Q.begin();
		u=z->second;

		Q.erase(z);
		viz[u]=1;

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

			if(viz[v]==0) {

				if(d[v]>w_uv){
					tata[v]=u;
			        Q.erase(make_pair(d[v],v)); //sterg perechea daca exista
					d[v]=w_uv;
  				    Q.insert(make_pair(d[v],v)); //adaug noua pereche v,d[v]
  				}
			}
		}

	}

	for(u=1;u<=n;u++)
		if(tata[u]!=0) {//u!=s{
			muchii_apcm.push_back({u,tata[u] });
			cost+=d[u];
			}
}
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;

}