#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int viz[200001],n,m,s,tt[200001],sz[200001];
vector<pair<int,pair<int,int>>> G;
vector<pair<int,int>> sol;
int root(int x)
{
    while(tt[x]!=0)
        x=tt[x];
    return x;
}
void un(int x, int y)
{
    int rx=root(x);
    int ry=root(y);
    if(sz[rx]>=sz[ry])
    {
        tt[ry]=rx;
        sz[rx]+=sz[ry];
    }
    else
    {
        tt[rx]=ry;
        sz[ry]+=sz[rx];
    }
}
int main()
{
	fin >> n >> m;
	for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        G.push_back(make_pair(c,make_pair(x,y)));
    }
    for(int i=1;i<=n;i++) sz[i]=1;
    sort(G.begin(),G.end());
    int k=0,cost=0,px=0;
    while(k<n-1)
    {
        int rx=root(G[px].second.first);
        int ry=root(G[px].second.second);
        if(rx!=ry)
        {
            k++;
            cost+=G[px].first;
            un(rx,ry);
            sol.push_back(G[px].second);
        }
        px++;
    }
    fout << cost << "\n" << n-1 << "\n";
    for(int i=0;i<k;i++)
        fout << sol[i].first << " " << sol[i].second << "\n";
	return 0;
}