#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100000
int edges[20000][3];
int size[20000];
int refs[20000];
int cnt=0;
int n=0, m=0;
int partialTree[20000][3];
void initialize()
{
ifstream in ("apm.in");
in>>n>>m;
for (int i=1;i<=m;i++)
in>>edges[i][0]>>edges[i][1]>>edges[i][2];
for (int i=1; i<=n; i++)
{
refs[i]=i;
size[i]=1;
}
cnt=n;
}
void sort()
{
int x, y, z,j;
for(int i=1;i<=m;i++)
{
j=i;
while(j>1&&edges[j][2]<edges[j-1][2])
{
x=edges[j][2];
y=edges[j][1];
z=edges[j][0];
edges[j][2]=edges[j-1][2];
edges[j][1]=edges[j-1][1];
edges[j][0]=edges[j-1][0];
edges[j-1][2]=x;
edges[j-1][1]=y;
edges[j-1][0]=z;
j--;
}
}
}
int find(int p)
{
int root = p;
while (root != refs[root])
root = refs[root];
while (p != root) {
int newp = refs[p];
refs[p] = root;
p = newp;
}
return root;
}
int merge(int x, int y)
{
int i = find(x);
int j = find(y);
//cout<<"se compara "<<i<<" cu "<<j;
if (i == j) return 0;
if (size[i] < size[j])
{
refs[i] = j;
size[j] += size[i];
}
else
{
refs[j] = i;
size[i] += size[j];
}
cnt--;
return 1;
}
int main()
{
/*int sum=0; //versiunea de consola
initialize();
for (int i=1;i<=m;i++)
{
cout<<edges[i][0]<<" "<<edges[i][1]<<" "<<edges[i][2]<<endl;
}
sort();
cout<<endl;
for (int i=1;i<=m;i++)
{
cout<<edges[i][0]<<" "<<edges[i][1]<<" "<<edges[i][2]<<endl;
}
int partialLengh=0;
for (int i=1;i<=m;i++)
{
if (merge(edges[i][0],edges[i][1])==1)
{
partialLengh++;
partialTree[partialLengh][0]=edges[i][0];
partialTree[partialLengh][1]=edges[i][1];
partialTree[partialLengh][2]=edges[i][2];
sum+=edges[i][2];
}
}
cout<<endl<<"Costul arborelui este de:"<<sum;
cout<<endl<<"Dimensiunea arborelui este de:"<<partialLengh;
cout<<endl<<"Arborele partial obtinut este format din laturile:"<<endl;
for (int i=1;i<=partialLengh;i++)
{
cout<<partialTree[i][0]<<" "<<partialTree[i][1]<<" de lungime "<<partialTree[i][2]<<endl;
}*/
int sum=0; //versiunea de infoarena
initialize();
sort();
int partialLengh=0;
for (int i=1;i<=m;i++)
{
if (merge(edges[i][0],edges[i][1])==1)
{
partialLengh++;
partialTree[partialLengh][0]=edges[i][0];
partialTree[partialLengh][1]=edges[i][1];
partialTree[partialLengh][2]=edges[i][2];
sum+=edges[i][2];
}
}
ofstream out("apm.out");
out<<sum<<endl;
out<<partialLengh<<endl;
for (int i=1;i<=partialLengh;i++)
{
out<<partialTree[i][0]<<" "<<partialTree[i][1]<<endl;
}
}