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

int n,i,j,m,x,y,c,nrc,sol,nrs;
vector<int> v[200005];
bool viz[200005];
int comp[200005];
struct muchie{
int x,y,c;}mu[400005],ans[400005];
bool cmp(muchie a, muchie b){
return a.c < b.c;}

void dfs(int nod)
{
    viz[nod]=1;
    for(auto node : v[nod])
        if(!viz[node]) dfs(node);
}
bool comp_dif(int x, int y)
{
    memset(viz,0,sizeof(viz));
        dfs(x);
    return !viz[y];
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=m;++i)
    {
        cin>>x>>y>>c;
        mu[i].x=x;
        mu[i].y=y;
        mu[i].c=c;
    }
    sort(mu+1,mu+m+1,cmp);

    sol+=mu[1].c;
    ans[1].x = mu[1].x;
    ans[1].y = mu[1].y;
    ++nrs;

    v[mu[1].x].push_back(mu[1].y);
    v[mu[1].y].push_back(mu[1].x);
    for(i=2;i<=m;++i)
    {
        if(comp_dif(mu[i].x,mu[i].y))
        {
            v[mu[i].x].push_back(mu[i].y);
            v[mu[i].y].push_back(mu[i].x);
            ++nrs;
            ans[nrs].x = mu[i].x;
            ans[nrs].y = mu[i].y;
            sol+=mu[i].c;
        }
    }

    cout<<sol<<"\n";
    cout<<nrs<<"\n";
    for(i=1;i<=nrs;++i)
        cout<<ans[i].x<<" "<<ans[i].y <<"\n";
    return 0;
}