using namespace std;

#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#define pb push_back
struct edge{
int x,y,c;
};
ofstream fout("apm.out");
edge a[400005];
vector<edge> q;
int T[200005],R[200005],sum,N,M;
void init()
{int i;

    for(int i=1;i<=N;i++)
    {
        T[i]=i;
        R[i]=1;
    }
}
int find(int x)
{int Rad,y;
    for(Rad=x;Rad!=T[Rad];Rad=T[Rad]);
    for(;x!=T[x];)
    {
        y=T[x];
        T[x]=Rad;
        x=y;
    }
    return Rad;
}

void unite(int x,int y)
{
    if(x!=y)
    {
        if(R[x]>R[y])
          T[y]=x;
          else T[x]=y;
        if(R[x]==R[y]) R[y]++;
    }

}
void solve()
{int i;
    for(i=1;i<=M;i++)
    {
        if(find(a[i].x)!=find(a[i].y))
        {
            unite(find(a[i].x),find(a[i].y));
            sum+=a[i].c;
            q.push_back(a[i]);
        }
    }
    fout<<sum<<"\n";
    fout<<N-1<<"\n";
    for(i=1;i<=N-1;i++)
      fout<<q[i-1].x<<" "<<q[i-1].y<<"\n";


}

bool cmp(edge i,edge j)
{

    return i.c<j.c;
}
void cit()
{int i;
    ifstream fin("apm.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
     fin>>a[i].x>>a[i].y>>a[i].c;
    fin.close();

}

int main()
{
    cit();
    sort(a+1,a+M+1,cmp);
    init();
    solve();
    fout.close();
    return 0;
}