#include <bits/stdc++.h>
#define ll long long
using namespace std;

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

const int N=2e5+5,M=4e5+5;
struct muchie
{
    int x,y,cost;
}v[M];
int t[N],rang[N];

void QuickSort(int st,int dr)
{
    if(st<dr)
    {
        int m=(st+dr)/2;
        swap(v[m],v[st]);

        int i=st,j=dr,d=0;
        while(i<j)
        {
            if(v[i].cost>v[j].cost)
            {
                swap(v[i],v[j]);
                d=1-d;
            }
            i+=d;//creste daca d == 1
            j-=1-d;//scade daca d == 0
        }
        QuickSort(st,i-1);
        QuickSort(i+1,dr);
    }
}

int Radacina(int nod)
{
    if(!t[nod]) return nod;
    int x=Radacina(t[nod]);
    t[nod]=x;
    return x;
}

void Reuniune(int nod1,int nod2)
{

    int rad1=Radacina(nod1),rad2=Radacina(nod2);
    if(rad1==rad2) return;

    if(rang[rad1]>rang[rad2])
    {
        t[rad2]=rad1;
    }
    else
    {
        t[rad1]=rad2;
        if(rang[rad1] == rang[rad2]) rang[rad2]++;
    }
}

vector<pair<int,int> >kruskal(int m,ll &s)
{
    vector<pair<int,int> >x;
    for(int i=1;i<=m;i++)
    {
        if(Radacina(v[i].x) != Radacina(v[i].y))
        {
            x.push_back(make_pair(v[i].x,v[i].y));
            s+=v[i].cost;
            Reuniune(v[i].x,v[i].y);
        }
    }
    return x;
}

int main()
{
    int n,m;
    in>>n>>m;

    for(int i=1;i<=n;i++) rang[i]=1;

    for(int i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].cost;

    QuickSort(1,m);

    ll sum=0;
    vector<pair<int,int> >sol=kruskal(m,sum);

    out<<sum<<'\n'<<sol.size()<<'\n';
    for(int i=0;i<sol.size();i++)
        out<<sol[i].first<<' '<<sol[i].second<<'\n';

    return 0;
}