#include <bits/stdc++.h>
using namespace std;
typedef struct{int x,y,c;} NIBAB;

bool comp(NIBAB a,NIBAB b)
{
    return a.c<b.c;
}
int l[200005],n,m,arbx[400005],arby[400005];

NIBAB e[400005];
void citire()
{
ifstream fin("apm.in");
fin>>n>>m;
for(int i=1;i<=m;i++)
fin>>e[i].x>>e[i].y>>e[i].c;
fin.close();
}

int main()
{int x,y;
citire();
for(int i=1;i<=n;i++) l[i]=i;
sort(e+1,e+m+1,comp);
int nr=0,i=1,cost=0;
while (nr<n-1)
{
if(l[e[i].x]!=l[e[i].y])
{
nr++;
cost+=e[i].c;
for(int j=1;j<=n;j++)
if (l[j]==l[e[i].x])
l[j]=l[e[i].y];
arbx[nr]=e[i].x;
arby[nr]=e[i].y;
}
i++;
}
ofstream fout("apm.out");
fout<<cost<<"\n";
fout<<nr<<"\n";
for (int q=1;q<=nr;q++)
    fout<<arby[q]<<' '<<arbx[q]<<"\n";
fout.close();
return 0;
}