#include <fstream>
#include <algorithm>
#include <vector>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector <pair <int, pair<int,int> > > G;
vector <pair <int,int> > sol;
int t[400050],m,n,cost;
int rad(int nod)
{
    if (t[nod]!=nod)
        t[nod]=rad(t[nod]);
    return t[nod];
}
int main()
{
    int i,x,y,c;
    in>>n>>m;
    for (i=1;i<=m;i++) {
        in>>x>>y>>c;
        G.pb(mp(c,mp(x,y)));
    }
    sort(G.begin(),G.end());
    for (i=1;i<=m;i++) t[i]=i;
    for (i=0;i<G.size();i++)
        {
            x=G[i].s.f;
            y=G[i].s.s;
            if (rad(x)!=rad(y))
            {
                t[t[y]]=t[x];
                cost+=G[i].f;
                sol.pb(mp(x,y));
            }
        }

    out <<cost<<'\n'<<n-1<<'\n';
    for (i=0;i<sol.size();i++) out<<sol[i].f<<' '<<sol[i].s<<'\n';
    return 0;
}