#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;
int t[400050],m,n,cost,sel[400050];
void reuneste(int x,int y)
{
    int i,z;
    z=t[y];
    if (t[x]==t[y]) return;
    for (i=1;i<=m;i++) if (t[i]==z) t[i]=t[x];
}
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 (t[x]!=t[y])
            {
                reuneste(x,y);
                cost+=G[i].f;
                sel[i]=1;
            }
        }

    out <<cost<<'\n'<<n-1<<'\n';
    for (i=0;i<=m;i++)
        if (sel[i]==1) out<<G[i].s.f<<' '<<G[i].s.s<<'\n';
    return 0;
}