#include<bits/stdc++.h>
#define fore(start,i,end) for(int i = start; i <= end; i++)
#define dbg(x)  #x << "=" << x << " "
#define dbg2(x,y)  "{" << x << "," << y << "} "
#define dbg3(x,y,k) "{" << x << "," << y << "," << k << "} "
#define dbg4(x,y,k,j) "{" << x << "," << y << "," << k << " , " << j << "} "

#define ll long long
#define f1 first
#define f2 second
#define inf 1000000005
#define debug_st(st) if (true) {cout << #st << " : "; stack<int> s123; while (!s123.empty()) cout << s123.top() << " ", s123.pop(); cout << "\n";}
#define debug_a(a,n) cout << #a << " : "; for(int i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n";
#define debug_m(a,n,m) cout << #a << " :\n"; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++) cout << a[i][j] << " "; cout << "\n"; }cout << "\n";
#define debug_v(v) cout << #v << " : "; for(auto k : v) cout << k << " "; cout << "\n";
#define debug_s(s) cout << #s << " : "; for (auto k : s) cout << k < " "; cout << "\n";
#define debug_s2(s) cout << #s << " : "; for(auto k : s) cout << dbg2((*k).first,(*k).second); cout << "\n";



using namespace std;

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

const int nmax = 200005;

int n,m,r[nmax],s[nmax];

vector<pair<int,int>> selected;
struct edge {
    int u,v,c;
};
vector<edge> muchii;

bool cmp(edge a, edge b)
{
    return (a.c < b.c);
}

int root(int x)
{
    if (r[x] == 0)
        return x;
    else {
        return (r[x] = root(r[x]));
    }
}

bool join(int x, int y) /// x si y sunt deja radacini.
{
    x = root(x);
    y = root(y);

    if (x == y)
        return false;

    if (s[x] > s[y]) /// x e mereu minim ca size
        swap(x,y);

    r[x] = y;
    s[y] += s[x];
    return true;
}
int main()
{int i,u,v,c,cost = 0;
    for (i = 1; i <= n; i++)
        s[i] = 1;

    in >> n >> m;
    //cout << dbg(n) << dbg(m) << "\n";
    for (i = 1; i <= m; i++) {
        in >> u >> v >> c;
        muchii.push_back({u,v,c});
    }
/*
    for (auto k : muchii) {
        cout << dbg(k.u) << dbg(k.v) << dbg(k.c) << "\n";
    }*/

    sort(muchii.begin() , muchii.end(), cmp);

    for (i = 0; i < muchii.size(); i++)
    {
        edge p = muchii[i];
        if (join(p.u , p.v))
        {
            cost += p.c;
            selected.push_back({p.u,p.v});
        }
    }

    out << cost << "\n";
    out << selected.size() << "\n";
    for (auto k : selected) {
        out << k.first << " " << k.second << "\n";
    }

    out << "\n";

}