#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> Pii;
typedef pair<int, pair<int, int> > Piii;
const int nmax=1e3;
int n, m;
int x, y, z;
vector <Piii> muchii;
ifstream in ("apm.in");
ofstream out("apm.out");
vector <bool> taken;
vector <int> fat;
int getFat(int nod){
    if(fat[nod]==nod) return nod;
    return fat[nod]=getFat(fat[nod]);
}
bool DsuUnion(int nod1, int nod2){
    nod1=getFat(nod1); nod2=getFat(nod2);
    if(nod1==nod2)
        return false;
    fat[nod2]=nod1;
    return true;
}
int main()
{
    in>>n>>m;
    for(int i=1; i<=m; i++){
        in>>x>>y>>z;
        muchii.push_back({z, {y, x}});
    }
    sort(muchii.begin(), muchii.end());
    taken.resize(m);
    fat.resize(n+1);
    for(int i=1; i<=n; i++)
        fat[i]=i;
    int ans=0;
    for(int i=0; i<m; i++)
        if(DsuUnion(muchii[i].second.first, muchii[i].second.second)==true)
            taken[i]=true, ans+=muchii[i].first;
    out<<ans<<"\n"<<n-1<<"\n";
    for(int i=0; i<m; i++)
        if(taken[i]==true)
            out<<muchii[i].second.first<<" "<<muchii[i].second.second<<"\n";
    return 0;
}