#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = uint64_t;
using pi = pair<int, int>;
using ti = tuple<int, int, int>;
using tl = tuple<ll, ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpl = vector<pl>;
using vti = vector<ti>;
using vtl = vector<tl>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvpi = vector<vpi>;
using vvpil = vector<vpil>;
using vvpli = vector<vpli>;
using vvpl = vector<vpl>;
using vvti = vector<vti>;
using vvtl = vector<vtl>;


#if 1
ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout
#endif


struct Edge
{
    int u,v,w;
    bool operator<(Edge const& o)
    {
        return w < o.w;
    }
};
const int nmx = 2e5 + 1;
int t[nmx];
int gr[nmx];
vector<Edge> edges;

int Root(int k)
{
    if(t[k] == 0)
        return k;
    int it = k;
    while(t[it])
    {
        it = t[it];
    }
    return it;
}

bool Unite(int n1, int n2)
{
    int r1 = Root(n1), r2 = Root(n2);
    if(r1 == r2)
        return false;
    else if(gr[r1] < gr[r2])
        t[r1] = r2;
    else if(gr[r2] < gr[r1])
        t[r2] = r1;
    else if(gr[r1] == gr[r2])
        t[r2] = r1, gr[r1]++;
    return true;
}

int main()
{
    int n,m;
    cin >> n >> m;
    edges = vector<Edge>(m);
    for(int i=0;i<m;i++)
    {
        Edge& e = edges[i];
        cin >> e.u >> e.v >> e.w;
    }
    sort(edges.begin(),edges.end());
    
    int ans = 0;
    
    vector<Edge> tree;
    
    for(auto& edg : edges)
    {
        if(Unite(edg.u,edg.v))
            ans += edg.w, tree.emplace_back(edg);
    }
    
    cout << ans << "\n" << tree.size() << '\n';
    for(auto& edg : tree)
        cout << edg.u << " " << edg.v << "\n";
    
}