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


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;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > Q;
	Q.push({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++){


		auto z=Q.top();
		Q.pop();
		u=z.second;
		while (viz[u]) {auto z=Q.top();Q.pop();
		u=z.second;};


		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;

					d[v]=w_uv;
  				    Q.push({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;

}