#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int , pair<int ,int > >
using namespace std;
const int MAX = 2e5 + 5;
int n , m , i , x , y , str[MAX] , c , cost;
pii p[2 * MAX];
vector <pair <int , int> > ans;
int dad(int x)
{
    if(x == str[x]) return x;
    return str[x] = dad(str[x]);
}
void u(int x , int y)
{
    x = dad(x);
    y = dad(y);
    str[x] = y;
}
int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        p[i] = {c ,{x , y}};
    }
    sort(p + 1 , p + 1 + m);
    for(i=1;i<=n;i++) str[i] = i;
    for(i=1; i<=m; i++)
    {

        x = dad(p[i].S.F);
        y = dad(p[i].S.S);
        if(x != y)
        {
            cost += p[i].F;
            ans.push_back({p[i].S.F , p[i].S.S});
            //fout << x << " " << y << " \n";
            str[x] = y;
        }
    }
    fout<<cost << "\n";
    fout << n-1 << "\n";
    for(i=0;i<ans.size();i++)
        fout << ans[i].F << " " << ans[i].S <<"\n";
    return 0;
}