#include<fstream>
#include<vector>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

constexpr int oo = 1e9;

class DSU
{
    private : vector<int> t;
    public : DSU(int n){t.resize(n + 1,0);}
    int root(int a){return t[a] ? t[a] = root(t[a]) : a;}
    void unite(int a,int b){t[a] = b;}
};

struct muchie
{
    int a,b,c;
    muchie(int& aa,int& bb,int& cc) : a(aa) , b(bb) , c(cc) {}
};

int main()
{
    int n,m,a,b,c,ans(0); cin >> n >> m;
    vector<muchie> muchii; muchii.reserve(m);
    for(int i = 0 ; i < m ; i++)
        {
            cin >> a >> b >> c;
            muchii.push_back(muchie(a,b,c));
        }

    c = oo; vector<int> id; id.reserve(n - 1);
    DSU padure(n); muchii.push_back(muchie(a,b,c));
    c = n; while(c > 1)
    {
        vector<int> comp(n + 1,m);
        for(int i = 0 ; i < m ; i++)
            {
                muchie &it = muchii[i];
                int ra = padure.root(it.a), rb = padure.root(it.b);
                if(ra != rb)
                    {
                        if(muchii[comp[ra]].c > it.c) comp[ra] = i;
                        if(muchii[comp[rb]].c > it.c) comp[rb] = i;
                    }
            }

        for(int i = 1; i <= n ; i++)
            {
                if(comp[i] == m) continue;
                int ra = padure.root(muchii[comp[i]].a) , rb = padure.root(muchii[comp[i]].b);
                if(ra != rb) ans += muchii[comp[i]].c , padure.unite(ra,rb) , c-- , id.emplace_back(comp[i]);
            }
    }

    cout << ans << '\n' << n - 1 << '\n';
    for(auto &it : id) cout << muchii[it].a << " " << muchii[it].b << '\n';
}