#include <bits/stdc++.h>

using namespace std;

ifstream fin("file.in");
ofstream fout("file.out");

const int N = 200001;
int n, m, t[N], x, y, c, cost;
vector< pair<int, int> > sol;
vector <tuple<int, int, int>> E;

int getRoot(int nodStart)
{
    if(t[nodStart] == nodStart)
        return nodStart;
    t[nodStart] = getRoot(t[nodStart]);
    return t[nodStart];
}


int main()
{
    fin>>n>>m;

    for(int i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        E.push_back(make_tuple(c, x, y));

    }

    sort(E.begin(), E.end());

    for(int i=1; i<=n; i++)
        t[i] = i;
    for(auto it : E)
    {
        int x, y, c;
        tie(c, x, y) = it;
        int rx = getRoot(x);
        int ry = getRoot(y);

        if(rx != ry)
        {
            t[rx] = ry;
            cost += c;
            sol.push_back(make_pair(x, y));
        }

    }

    fout<<cost<<'\n'<<n-1<<'\n';

    for(int i=0; i<sol.size(); i++)
        fout<<sol[i].second<<" "<<sol[i].first<<endl;


    return 0;
}