// kruskal
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
#define mp make_pair
using namespace std;

const int NMAX = 200010;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,i,x,y,z,P[NMAX],sum=0;
vector < pair<int,pair<int,int> > > g;
vector < pair <int, int> > sol;
int findset(int a)
{
    return (a==P[a]) ? a : (P[a]=findset(P[a]));
}

int main()
{
    cin>>n>>m;
    int k=m;
    while (k--)
    {
        cin>>x>>y>>z;
        g.pb(mp(z,mp(x,y)));
    }
    for (i=1;i<=n;i++) P[i]=i;
    sort(g.begin(),g.end());
    for (i=0;i<m;i++)
    {
        int a=g[i].second.first, b=g[i].second.second, cost=g[i].first;
        int fa=findset(a), fb=findset(b);
        if (fa!=fb)
        {

            sum+=cost;
            sol.pb(mp(a,b));
            P[fa]=fb;
        }
    }
    cout<<sum<<"\n"<<n-1<<"\n";
    for (i=0;i<sol.size();i++) cout<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;

}