#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m;
int x,y,c;
int costAPM;
vector<pair<pair<int,int>,int> > M;
vector<pair<int,int> > Msol;
int tata[200005],nrel[200005];

int comp(const pair<pair<int,int>,int>& i,const pair<pair<int,int>,int>& j){

    return i.second<j.second;

}

int Find(int x){

    if(tata[x]==x)
        return x;

    tata[x]=Find(tata[x]);

    return tata[x];

}

void Merge(int x,int y){

    if(nrel[x]>nrel[y]) swap(x,y);

    nrel[y]+=nrel[x];
    tata[x]=y;

}

int main(){

    cin>>n>>m;
    for(int i=1;i<=m;i++){

        cin>>x>>y>>c;
        M.push_back(make_pair(make_pair(x,y),c));

    }

    sort(M.begin(),M.end(),comp);

    int cnt=1;

    for(int i=1;i<=n;i++)
        tata[i]=nrel[i]=i;

    for(int i=0;i<M.size() && cnt<n;i++){

        int f1=Find(M[i].first.first);
        int f2=Find(M[i].first.second);

        if(f1!=f2){

            Merge(f1,f2);
            ++cnt;
            costAPM+=M[i].second;
            Msol.push_back(make_pair(M[i].first.first,M[i].first.second));


        }

    }

    cout<<costAPM<<'\n'<<n-1<<'\n';
    for(int i=0;i<Msol.size();i++)
        cout<<Msol[i].first<<' '<<Msol[i].second<<'\n';

}