#include <bits/stdc++.h>

#define ll long long
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
ll supremus[100002],n,m,op,x,y,sz[100002];

struct ceva{
    int x , y , cost;
};
ceva muchie[400002];


ll fnd(ll x)
{
    if(supremus[x]!=x)
        supremus[x]=fnd(supremus[x]);
    return supremus[x];
}
void unite(int x , int y)
{
    int tx = fnd(x);
    int ty = fnd(y);
    supremus[tx] = ty;
}

bool comp(ceva m1 , ceva m2)
{
    return m1.cost<m2.cost;
}
vector<pair<int,int>>v;
int main()
{

    fin>>n>>m;
    for(ll i=1;i<=n;i++)
        {supremus[i]=i;
        sz[i]=1;}

    for(ll i=1;i<=m;i++)
    {
        fin>>muchie[i].x>>muchie[i].y>>muchie[i].cost;
    }
    sort( muchie+1 , muchie+1+m , comp);

    int s=0;
    for(int i=1;i<=m;i++)
    {
        if(fnd(muchie[i].x)!=fnd(muchie[i].y))
        {
            s+=muchie[i].cost;
            unite(muchie[i].x ,muchie[i].y);
            v.push_back({muchie[i].x , muchie[i].y});
        }
    }
    fout<<s<<'\n';
    fout<<v.size()<<'\n';
    for(int i=0;i<v.size();i++)
        fout<<v[i].first<< ' '<<v[i].second<<'\n'   ;
    return 0;
}