#include <bits/stdc++.h>
#define ll long long
#define lf long double

using namespace std;

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

vector<pair<int,pair<int,int>>> apm;
vector<pair<int,int>> rasp;
int n,m,x,y,c,cost,par[200005];

int getpar(int nod)
{
    if (par[nod]==nod)
        return nod;
    else
    {
        par[nod]=getpar(par[nod]);
        return par[nod];
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        apm.push_back({c,{x,y}});
    }
    sort(apm.begin(), apm.end());
    for (int i=1;i<=n;i++)
        par[i]=i;
    for (auto mu:apm)
    {
        pair<int,int> cap=mu.second;
        if (getpar(cap.first)!=getpar(cap.second))
        {
            cost+=mu.first;
            par[getpar(cap.second)]=getpar(cap.first);
            rasp.push_back(cap);
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for (auto mu:rasp)
        fout<<mu.first<<" "<<mu.second<<'\n';
    return 0;
}

//Long long output!!!
//Check constraints!!!