#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

#define pb push_back
#define mp make_pair
#define Nmax 100003

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

int n,m,i,a,b,c,Cost,p[Nmax];
vector<pair<int,int> > sol;
vector< pair <int, pair<int,int> > > g;

int find(int x)
{
    return (x==p[x]) ? x : p[x]=find(p[x]);
}

int main()
{
    cin>>n>>m;
    while (m--) cin>>a>>b>>c, g.pb(mp(c,mp(a,b)));
    sort(g.begin(),g.end());
    for (i=1;i<=n;i++)p[i]=i;

    for (i=0;i<g.size();i++)
    {
        a=g[i].second.first, b=g[i].second.second,c=g[i].first;
        int pa=find(a), pb=find(b);
        if (pa!=pb) {
            p[pa]=pb;
            sol.pb(mp(a,b));
            Cost+=c;
        }
    }
    cout<<Cost<<'\n'<<n-1<<'\n';
    for (i=0;i<sol.size();i++)
        cout<<sol[i].first<<' '<<sol[i].second<<'\n';
    return 0;
}