#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int N , M;
vector<pair<int,pair<int,int>>>Muchii;
vector<int>T;

int Tata(int NodCrt){
     if(T[NodCrt] == 0) return NodCrt;
     return T[NodCrt]=Tata(T[NodCrt]);
 }

int main()
{
cin>>N>>M;
T.resize(N+1,0);
Muchii.resize(M);
for(int i=0 ; i<M ; i++){
    cin>>Muchii[i].second.first>>Muchii[i].second.second>>Muchii[i].first;
 }

sort(Muchii.begin() , Muchii.end());
vector<pair<int,int>>V;
long long S=0;
for(int i=0 ; i<M ; i++){
    int Nod1 , Nod2 , Cost;
    Nod1=Muchii[i].second.first;
    Nod2=Muchii[i].second.second;
    Cost=Muchii[i].first;
    int P1=Tata(Nod1);
    int P2=Tata(Nod2);
    if(P1 != P2){
         T[P1]=P2;
         V.push_back({Nod1,Nod2});
         S+=Cost;
    }
 }

cout<<S<<'\n';
cout<<N-1<<'\n';
for(auto [a,b] : V){
     cout<<a<<' '<<b<<'\n';
 }
return 0;
}