#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef struct
{
    int v1,v2,cost;
} wEdge;
 
istream& operator >>(istream& i, wEdge& e)
{
    i>>e.v1>>e.v2>>e.cost;
    e.v1--;
    e.v2--;
    return i;
}
 
ostream& operator <<(ostream& o, wEdge& e)
{
    o<<e.v1+1<<' '<<e.v2+1;
    return o;
}
 
bool operator <(const wEdge& e1, const wEdge& e2)
{
    if(e1.cost<e2.cost) return 1;
    return 0;
}
 
bool operator ==(const wEdge& e1, const wEdge& e2)
{
    if(e1.cost==e2.cost) return 1;
    return 0;
}
 
int vertexRank(const int& v, const vector<int>& parent)
{
    int rank=0;
    for(unsigned int i=0;i<parent.size();i++)
    {
        if(parent[i]==v) rank++;
    }
    return rank;
}
 
int find(const int& v, vector<int>& parent)
{
	if(parent[v]!=v) parent[v]=find(parent[v],parent);
	return parent[v];
}

void Union(const int& v1, const int& v2, vector<int>& parent, vector<int>& rank)
{
	if(rank[parent[v1]]>=rank[parent[v2]])
	{
		rank[v1]++;
		rank[parent[v2]]=0;
		parent[find(v2,parent)]=v1;
	}
	else
	{
		rank[v2]++;
		rank[parent[v2]]=0;
		parent[find(v1,parent)]=v2;
	}
	/*
    if(vertexRank(v1,parent)>vertexRank(v2,parent))
    {
        for(unsigned int i=0;i<parent.size();i++)
        {
            if(parent[i]==parent[v2] && i!=v2) parent[i]=parent[v1];
        }
        parent[v2]=parent[v1];
    }
    else
    {
        for(unsigned int i=0;i<parent.size();i++)
        {
            if(parent[i]==parent[v1] && i!=v1) parent[i]=parent[v2];
        }
        parent[v1]=parent[v2];
    }
	*/
}
 
bool compWEdges(const wEdge& e1, const wEdge& e2) {return e1<e2;}
 
int main()
{
    ifstream fin("apm.in");
    int N,M,i,costTotal=0;
    wEdge aux;
    vector<wEdge> graph;
    vector<wEdge> kruskal;
    vector<int> parent,rank;
    fin>>N>>M;
    graph.resize(M);
    parent.resize(M,0);
	rank.resize(M,1);
    for(i=0;i<M;i++) fin>>graph[i];
    for(i=0;i<N;i++) parent[i]=i;
    fin.close();
    sort(graph.begin(),graph.end(),compWEdges);
    for(i=0;i<M;i++)
    {
        //cout<<"Checking the edge "<<graph[i].v1+1<<'-'<<graph[i].v2+1<<" of cost "<<graph[i].cost<<". ";
        //if(parent[graph[i].v1]!=parent[graph[i].v2])
        if(find(graph[i].v1,parent)!=find(graph[i].v2,parent))
		{
            //cout<<"Parent of "<<graph[i].v1+1<<" is "<<parent[graph[i].v1]<<" and parent of "<<graph[i].v2<<" is "<<parent[graph[i].v2]<<".\n";
            kruskal.push_back(graph[i]);
            Union(graph[i].v1,graph[i].v2,parent,rank);
            costTotal+=graph[i].cost;
        }
    }
    ofstream fout("apm.out");
    fout<<costTotal<<'\n'<<kruskal.size()<<'\n';
    for(i=0;i<kruskal.size();i++) fout<<kruskal[i]<<'\n';
    fout.close();
    return 0;
}