#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct elem2
{
    int nod, cost;
};
struct elem
{
    int nod1, nod2, cost;
    bool operator < (const elem & other) const
    {
        return cost>other.cost;
    }
};
priority_queue <elem> pq;
vector <elem2> v[200009];
int n, sol[200009], k;
vector <elem> ans;
bool viz[200009];
void prim ()
{
    while (!pq.empty())
    {
        elem x=pq.top();
        pq.pop();
        //cout << x.nod1 << ' ';
        if (!viz[x.nod1] || !viz[x.nod2])
            ans.push_back(x);
        viz[x.nod1]=viz[x.nod2]=1;
        for (auto y:v[x.nod1])
        {
            if (!viz[y.nod]) pq.push({x.nod1, y.nod, y.cost});
        }
        for (auto y:v[x.nod2])
        {
             if (!viz[y.nod]) pq.push({x.nod2, y.nod, y.cost});
        }
    }
}
signed main ()
{
    int m;
    f >> n >> m;
    elem first={1000000, 1000000, 10000000};
    for (int i=1; i<=m; i++)
    {
        int x, y, z;
        f >> x >> y >> z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
        if (z<first.cost)
        {
            first={x,y,z};
        }
    }
    pq.push(first);
    //cout << first.cost << ' ';
    prim ();
    int s=0;
    for (int i=0; i<ans.size(); i++)
        s+=ans[i].cost;
    g << s << '\n' << ans.size() << '\n';
    for (int i=0; i<ans.size(); i++)
        g << ans[i].nod1 << ' ' << ans[i].nod2 <<'\n';

}