#include <iostream>
#include<fstream>
#include<algorithm>
#define Nmax 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
pair <int,int> APM[Nmax];
int n,m,cost,C[Nmax],k,RG[Nmax];

struct edge
{
    int x,y,c;
};
edge E[Nmax];

bool cmp(edge a,edge b)
{
    return a.c<b.c;
}

void read()
{
    fin>>n>>m;
    int i;
    for(i=1;i<=m;i++)
        fin>>E[i].x>>E[i].y>>E[i].c;
    sort(E+1,E+m+1,cmp);
}

 void init()
 {
     int i;
     for(i=1;i<=m;i++)
     {
         C[i]=i;
         RG[i]=1;
     }

 }

int find(int nod)
{
    while(C[nod]!=nod)
        nod=C[nod];
    return nod;
}

void unite(int x,int y)
{
    if(RG[x]<RG[y])
        C[x]=y;
    if(RG[y]<RG[x])
        C[y]=x;
    if(RG[x]==RG[y])
        C[x]=y,RG[y]++;
}
void solve()
{
    int i;
    for(i=1;i<=m;i++)
        if(find(E[i].x)!=find(E[i].y))
        {
            unite(find(E[i].x),find(E[i].y));
            k++;
            APM[k].first=E[i].x;
            APM[k].second=E[i].y;
            cost+=E[i].c;
        }
}


 void afis()
 {
     fout<<cost<<"\n";
    fout<<n-1<<"\n";

    for(int i=1;i<=k;i++)
        fout<<APM[i].second<<" "<<APM[i].first<<"\n";
 }

int main()
{
    read();
    init();
    solve();
    afis();

    return 0;
}