#include <bits/stdc++.h>
#define z(x) (x & (-x))
typedef long long ll;
using namespace std;

ll sum, n, m, p[200100], R[200100], r;
struct my{int x, y, c;} A[200100];
int find(int a){return (p[a] == a ? a : p[a] = find(p[a]));}
void unite(int a, int b){p[find(b)] = find(a);}
bool cmp(my a, my b){return a.c < b.c;}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> A[i].x >> A[i].y >> A[i].c;
    for (int i = 1; i <= n; i++) p[i] = i;
    sort(A+1, A+m+1, cmp);
    for (int i = 1; i <= m; i++) if(find(A[i].x) != find(A[i].y)) sum += A[i].c, R[++r] = i, unite(A[i].x, A[i].y);
    cout << sum << "\n" << r << "\n";
    for (int i = 1; i <= r; i++) cout << A[R[i]].x << " " << A[R[i]].y << "\n";
    return 0;
}