#include <bits/stdc++.h>
using namespace std;

#define ll unsigned long long
#define fast_read ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define INF 0x3f3f3f3f

const int maxn = 2e5;
const int maxm = 4e5;
const int mod = 666013;
ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, cnt;
bitset<maxm + 1> vis;
int t[maxn + 2], rang[maxn + 2];
int ans;
struct edge{
    int x, y, cost;
} a[maxn + 2];
void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        fin >> a[i].x >> a[i].y >> a[i].cost;
    }

}
bool cmp(edge x1, edge y1){
    return (x1.cost < y1.cost);
}
int get_root(int i){
    if(t[i] == i)
        return i;
    return t[i] = get_root(t[i]);
}
void unite(int r1, int r2){
    if(rang[r1] > rang[r2])
        t[r2] = r1;
    else{
        t[r1] = r2;
        if(rang[r1] == rang[r2])
            rang[r1] ++;
    }
}
void solve(){
    for(int i = 1; i <= n; ++i) rang[i] = 1, t[i] = i;
    sort(a + 1, a + m + 1, cmp);
    for(int i = 1; i <= m; ++i){
        int r1 = get_root(a[i].x);
        int r2 = get_root(a[i].y);
        if(r1 != r2){
            vis[i] = 1;
            cnt++;
            ans += a[i].cost;
            unite(r1, r2);
        }
    }
    fout << ans << '\n' << cnt << "\n";
    for(int i = 1; i <= m; ++i)
        if(vis[i]) fout << a[i].x << " " << a[i].y << "\n";
}
int main(){
    read();
    solve();
    return 0;
}
/*


 */