#include <bits/stdc++.h>


using namespace std;
vector<int>G[1001];
int n,m,tablou[200001],f[200001];
struct abc{
    int i; int j; int cost;
}v[400005];
bool cmp(abc a,abc b){
    return a.cost<b.cost;
}
ifstream fin("apm.in");
ofstream fout("apm.out");
int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>v[i].i>>v[i].j>>v[i].cost;

    }
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++){
        tablou[i]=i;
        G[i].push_back(i);
    }
    int S=0;
    for(int i=1;i<=m;i++)
    if(tablou[v[i].i]!=tablou[v[i].j]){
        S+=v[i].cost;
        int ai = tablou[v[i].i];
        int aj = tablou[v[i].j];
        while(G[aj].size()){
            int x = G[aj][G[aj].size()-1];
            tablou[x]=ai;
            G[ai].push_back(x);
            G[aj].pop_back();
        }
    }
    else
        f[i]=1;
    int cnt=0;
    fout<<S<<'\n';
    for(int i=1;i<=m;i++)
        if(!f[i])
            cnt++;
    fout<<cnt<<'\n';
    for(int i=1;i<=m;i++)
        if(!f[i])
            fout<<v[i].i<<" "<<v[i].j<<'\n';
    return 0;
}