#include <bits/stdc++.h>
using namespace std;

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

struct tupl
{
    int first;
    int second;
    int cost;
};

int parent[200002];
int rang[200002];
vector<tupl> muchii;
vector<tupl> sol;

bool cmp(tupl a, tupl b)
{
    return a.cost < b.cost;
}

int findParent(int i)
{
    if (parent[i] == i)
        return i;

    return parent[i] = findParent(parent[i]);
}

void uniteNodes(int x, int y)
{
    int s1 = findParent(x);
    int s2 = findParent(y);

    if (s1 != s2)
    {
        if (rang[s1] < rang[s2])
        {
            parent[s1] = s2;
            rang[s2] += rang[s1];
        }
        else
        {
            parent[s2] = s1;
            rang[s1] += rang[s2];
        }
    }
}




int main()
{
    int n,m,a,b,c,ans = 0;
    fin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b>>c;
        tupl temp;
        temp.first = a;
        temp.second = b;
        temp.cost = c;
        muchii.push_back(temp);
    }
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        rang[i] = 1;
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for(int i=0; i<muchii.size(); i++)
    {
        int nod1 = muchii[i].first;
        int nod2 = muchii[i].second;
        if(findParent(nod1) != findParent(nod2))
        {
            uniteNodes(nod1, nod2);
            sol.push_back(muchii[i]);
            ans += muchii[i].cost;
        }
    }
    fout<<ans<<'\n'<<sol.size()<<'\n';
    for(int i=0; i<sol.size(); i++)
    {
        fout<<sol[i].first<<' '<<sol[i].second<<'\n';
    }
    return 0;
}