#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

vi parent(200005);
vi size(200005);
vector<vi> edges;

void make_set(int v){
    size[v] = 1;
    parent[v] = v;
}

int find_set(int v){
    if(parent[v] == v)
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(size[a] < size[b])
            swap(a, b);
        size[a] += size[b];
        parent[b] = a;
    }
}

void Kruskal(){
    sort(edges.begin(), edges.end());
    vector<pi> MST;
    int sum = 0;
    for(auto edge : edges){
        int w = edge[0];
        int a = edge[1];
        int b = edge[2];
        if(find_set(a) != find_set(b)){
            sum += w;
            union_sets(a, b);
            MST.pb({a, b});
        }
    }
    cout << sum << '\n';
    cout << MST.size() << '\n';
    for(auto i : MST)
        cout << i.f << ' ' << i.s << '\n';
}
 
void solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        make_set(i);
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        edges.pb({w, a, b});
    }
    Kruskal();
}  
 
int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}