#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("apm.in");
ofstream fout("apm.out");
int n,m,i,j,T[200001],sol,S[400001],nr;
struct elem
{
    int x,y,cost;
}a[400001];
bool cmp(elem a,elem b)
{
    if(a.cost!=b.cost)
        return a.cost<b.cost;
    else
        if(a.x!=b.x)
            return a.x<b.x;
        else
            return a.y<b.y;
}
int get_root(int x)
{
    int c=x;
    while(T[x]>0)
        x=T[x];
    int node=c;
    while(node!=x)
    {
        c=T[node];
        T[node]=x;
        node=c;
    }
}
void join(int x,int y)
{
    int root_a=get_root(x);
    int root_b=get_root(y);
    if(T[root_a]>T[root_b])
        swap(root_a,root_b);
    T[root_a]+=T[root_b];
    T[root_b]=root_a;
}
bool query(long long x,long long y){return get_root(x)==get_root(y);}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;i++)
        fin>>a[i].x>>a[i].y>>a[i].cost;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=n;i++)
        T[i]=-1;
    for(i=1;i<=m;i++)
    {
        if(!query(a[i].x,a[i].y))
        {
            sol+=a[i].cost;
            join(a[i].x,a[i].y);
            S[++nr]=i;
            if(nr==n-1)
                break;
        }
    }
    fout<<sol<<"\n";
    fout<<n-1<<"\n";
    for(i=1;i<=nr;i++)
        fout<<a[S[i]].x<<" "<<a[S[i]].y<<"\n";
    return 0;
}