#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define nmax 200999
using namespace std;
int t[nmax],h[nmax],n;
struct muc{
int x,y,c;
friend bool operator>(const muc&a,const muc&b);
};
bool operator>(const muc& a,const muc& b){
    return a.c> b.c;
}

vector <muc> sol;
priority_queue<muc,vector<muc> ,greater<muc> > H;

ifstream fin("apm.in");
ofstream fout("apm.out");

void citire(){
int m,i;
fin>>n>>m;
muc mu;
for(i=0;i<m;i++)
{fin>>mu.x>>mu.y>>mu.c;
 H.push(mu);
}
}

int Find(int x){
int r=x;
while(t[r]){
    r=t[r];
}
int q=x;
while(t[x]){
    q=t[x];
    t[x]=r;
    x=q;
}
return r;
}

void Union(int x,int y){
if(h[x]>h[y])t[y]=x;
else {t[x]=y;
    if(h[x]==h[y])h[y]++;
}
}


int main(){
int c1,c2;
muc m;
int cmin=0;
citire();
while(sol.size() < n-1){
    m=H.top();
    H.pop();

    c1=Find(m.x);
    c2=Find(m.y);
    if(c1!=c2){
    sol.push_back(m);
     Union(c1,c2);
     cmin+=m.c;
    }
}
fout<<cmin<<'\n'<<n-1<<'\n';
for(int i=0;i<sol.size();i++)
    fout<<sol[i].x<<' '<<sol[i].y<<'\n';
}