#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back

// boruvka

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
using pii = pair<int,int>;
const int nmax = 2e5 + 3;
int n , m , x , y , z , mn[nmax] , c[nmax*2];
bool tk[nmax*2];
struct edge
{
    int x , y , c , idx;
};
vector <edge> e;
struct dsu
{
    int t[nmax];
    int rad( int x )
    {
        if(!t[x]) return x;
        t[x] = rad(t[x]);
        return t[x];
    }
    void un( int x , int y )
    {
        x = rad(x);
        y = rad(y);
        if(x!=y) t[x] = y;
    }
}uf;
signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> z;
        e.pb({x,y,z,i});
        c[i] = z;
    }
    int cc = n;
    int mst = 0;
    c[0] = 1e9;
    while(cc>1)
    {
        for(int i = 1 ; i <= n ; ++i) mn[i] = 0;
        for(auto &it : e)
        {
            if(tk[it.idx] || uf.rad(it.x)==uf.rad(it.y)) continue;
            if(it.c<c[mn[uf.rad(it.x)]]) mn[uf.rad(it.x)] = it.idx;
            if(it.c<c[mn[uf.rad(it.y)]]) mn[uf.rad(it.y)] = it.idx;
        }
        for(int i = 1 ; i <= n ; ++i)
        {
            if(uf.rad(i)==i && !tk[mn[i]])
            {
                tk[mn[i]] = 1;
                mst += c[mn[i]];
                uf.un(e[mn[i]-1].x,e[mn[i]-1].y);
                cc--;
            }
        }
    }
    cout << mst << '\n' << n - 1 << '\n';
    for(int i = 1 ; i <= m ; ++i)
    {
        if(tk[i]) cout << e[i-1].x << ' ' << e[i-1].y << '\n';
    }
    return 0;
}