#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
using namespace std;
using pii = pair<int,int>;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n , m;
const int nmax = 2e5 + 1;
struct edge
{
    int x , y , c;
};
vector <edge> v;
struct dsu
{
    int t[nmax] , sz[nmax];
    void init()
    {
        for(int i = 1 ; i <= n ; ++i)
        {
            t[i] = 0;
            sz[i] = 1;
        }
    }
    int findc(int x)
    {
        if(!t[x]) return x;
        return t[x] = findc(t[x]);
    }
    void un(int x , int y)
    {
        if(sz[x] > sz[y])
        {
            sz[x] += sz[y];
            t[y] = x;
        }
        else
        {
            sz[y] += sz[x];
            t[x] = y;
        }
    }
}uf;
signed main()
{
    int x , y , c;
    cin >> n >> m;
    for(int i = 1 ; i <= m ; ++i)
    {
        cin >> x >> y >> c;
        v.push_back({x,y,c});
    }
    sort(v.begin(),v.end(),[](edge a , edge b){return a.c < b.c;});
    vector <pii> ans;
    int t = 0;
    for(auto it : v)
    {
        x = uf.findc(it.x);
        y = uf.findc(it.y);
        if(x == y) continue;
        t += it.c;
        uf.un(x,y);
        ans.push_back({it.x,it.y});
    }
    cout << t << '\n' << ans.size() << '\n';
    for(auto it : ans) cout << it.first << ' ' << it.second << '\n';
    return 0;
}