#include<bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int N = 2e5;
array <int,3> e[N];
struct DSU{
    int p,sz;
}dsu[N];
vector <pair<int,int>> ans2;
int leader(int x){
    if(x == dsu[x].p)return x;
    return dsu[x].p = leader(dsu[x].p);
}
void connect(int u,int w){
    u = leader(u);
    w = leader(w);
    if(u == w)return;
    if(dsu[u].sz > dsu[w].sz)swap(w,u);
    dsu[u].p = w;
    dsu[w].sz+=dsu[w].sz;
}
int main(){
    int n,m;
    fin>>n>>m;
    for(int i = 0;i < m;i++){
        int u,w,c;
        fin>>u>>w>>c;
        u--;w--;
        e[i] = {c,u,w};
    }
    for(int i = 0;i < n;i++){
        dsu[i] = {i,1};
    }
    sort(e,e + m);
    int ans = 0;
    for(int i = 0;i < m;i++){
        if(leader(e[i][1]) != leader(e[i][2])){
            connect(e[i][1],e[i][2]);
            ans+=e[i][0];
            ans2.push_back({e[i][1] + 1,e[i][2] + 1});
        }
    }
    fout<<ans<<'\n'<<n - 1<<'\n';
    for(auto i:ans2){
        fout<<i.first<<' '<<i.second<<'\n';
    }
    return 0;
}