#include <bits/stdc++.h>
#define nmax 200005
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int f[nmax*2];
int h[nmax*2];

struct muchie
{
    int a,b,c;
    muchie(int a=0,int b=0, int c=0)
    {
        this->a=a;
        this->b=b;
        this->c=c;
    }
    bool operator <(muchie other)
    {
        return c<other.c;
    }
} muchii[nmax*2];

int getroot(int nod)
{
    if(!f[nod])return nod;
    int tmp=getroot(f[nod]);
    f[nod]=tmp;
    return tmp;
}

void merge(int a,int b)
{
    int ra=getroot(a);
    int rb=getroot(b);
    if(h[ra]>h[rb])
    {
        f[ra]=rb;
    }
    else
    {
        f[rb]=ra;
        h[ra]+=(h[ra]==h[rb]);
    }
}

vector<pair<int,int>> rez;

int main()
{
    int n,m;
    in>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f[i]=i+n;
    }
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        in>>a>>b>>c;
        muchii[i]=muchie(a,b,c);
    }
    sort(muchii,muchii+m);
    int res=0;
    for(int i=0;i<m;i++)
    {
        int a=muchii[i].a;
        int b=muchii[i].b;
        if(getroot(a)!=getroot(b))
        {   
            merge(a,b);
            res+=muchii[i].c;
            rez.push_back({a,b});
        }
    }
    out<<res<<'\n';
    out<<rez.size()<<'\n';
    for(auto i:rez)
    {
        out<<i.first<<' '<<i.second<<'\n';
    }
}