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

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

int n,m,tata[200001],costul;
vector<pair<int,int>>muchii;
struct ura{
    int first,second,cost;
}v[400001];

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

int root(int nod)
{
    if(tata[nod] == nod)
        return nod;
    else
        return tata[nod] = root(tata[nod]);
}

void unite(int x, int y)
{
    int root1 = root(x);
    int root2 = root(y);
    if(root1 != root2)
        tata[root1] = root2;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        tata[i] = i;
    for(int i = 1; i <= m; i++)
    {
        int st,dr,cost;
        fin >> v[i].first >> v[i].second >> v[i].cost;
    }
    sort(v+1,v+m+1,cmp);
    for(int i = 1; i <= m; i++)
    {
        int root1=root(v[i].first);
        int root2=root(v[i].second);
        if(root1 != root2)
        {
            costul += v[i].cost;
            unite(root1,root2);
            muchii.push_back({v[i].first,v[i].second});
        }
    }
    fout << costul << '\n' << muchii.size() << '\n';
    for(auto i : muchii)
        fout << i.first << ' ' << i.second << '\n';
    return 0;
}