#include <bits/stdc++.h>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
#define pb push_back
#define mp make_pair
const int MAXN=400001;
int n,m;
int ver[MAXN];
vector<int>g[MAXN],g1[MAXN];
vector <pair<int,pair<int,int>>>gu;
vector <pair<int,int>>gs;
void dfs(int nod){
    if(ver[nod])
        return ;
    ver[nod]=1;
    for(auto y:g1[nod])
        dfs(y);
}
int main()
{
    in>>n>>m;
    int x,y,c;
    for(int i=0;i<m;i++){
        in>>x>>y>>c;
        g[x].pb(y);
        g[y].pb(x);
        gu.pb(mp(c,mp(x,y)));
    }
    int nr=n,ans=0;
    sort(gu.begin(),gu.end());
    for(int i=0;i<m;i++){
        int cost=gu[i].first;
        x=gu[i].second.first;
        y=gu[i].second.second;
        memset(ver,0,sizeof(ver));
        dfs(x);
        if(!ver[y]){
            nr--;
            g1[x].pb(y);
            g1[y].pb(x);
            gs.pb(mp(x,y));
            ans+=cost;
        }
        if(nr==1)
            break;
    }
    out<<ans<<'\n'<<n-1<<'\n';
    for(auto y:gs)
    out<<y.first<<' '<<y.second<<'\n';
    return 0;
}