#include <bits/stdc++.h>
#define int64 long long
#define pb push_back
#define mp make_pair
#define INF numeric_limits<int>::max()
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector< pair< int , pair<int,int> > > v;
vector< pair<int,int> > sol;
vector<int> comp;
int main()
{
    int n,m;
    in>>n>>m;
    for(;m;m--)
    {
        int x,y,z;
        in>>x>>y>>z;
        v.pb(mp(z,mp(x,y)));
    }
    sort(v.begin(),v.end());
    for(int i=0;i<=n;i++)
        comp.pb(i);
    int cost=0;
    for(int step=0,i=0;step!=n-1;)
    {
        if(comp[v[i].second.first]!=comp[v[i].second.second])
        {
            cost+=v[i].first;
            int mx=max(comp[v[i].second.first],comp[v[i].second.second]),mn=min(comp[v[i].second.first],comp[v[i].second.second]);
            for(int j=1;j<=n;j++)
            if(comp[j]==mn)
                comp[j]=mx;
            sol.pb(v[i].second);
            step++;
        }
        i++;
    }
    out<<cost<<'\n'<<n-1<<'\n';
    for(auto i: sol)
        out<<i.first<<' '<<i.second<<'\n';
    return 0;
}