#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;

struct mere{
int x , y , c;
bool operator <(mere b){
return c < b.c;
}
}A[4 * nmax + 5];

int n , m , c = 0, curr = 0;

int T[2 * nmax + 5];

vector <int> ans;

int rad(int nod){
curr++;
if(T[nod] == nod)return nod;
int k = rad(T[nod]);
T[nod] = k;
return k;
}


int main()
{
    freopen("apm.in" , "r" , stdin);
    freopen("apm.out" , "w" ,stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    cin >> n >> m;
    for(int i = 1;i <= m; ++i)
        cin >> A[i].x >> A[i].y >> A[i].c;
    sort(A + 1,A + 1 + m);
    for(int i = 1;i <= n; ++i)T[i] = i;
    for(int i = 1;i <= m; ++i){
        curr = 0;
        int r1 = rad(A[i].x);
        int c1 = curr;
        curr = 0;
        int r2 = rad(A[i].y);
        int c2 = curr;
        if(r1 != r2){
            c += A[i].c;
            if(c1 > c2)
                T[A[i].y] = A[i].x;
            else T[A[i].x] = A[i].y;
            ans.push_back(i);
        }
    }
    cout << c << "\n";
    cout << ans.size() << "\n";
    for(auto i:ans)
        cout << A[i].x << " " << A[i].y << "\n";

}