#include <bits/stdc++.h>
#define cin fin
#define cout fout
#define eb emplace_back
using namespace std;

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

struct muchie
{
int x, y, cost;
};

vector<muchie> m, apm;

bool cmp(muchie x, muchie y)
{
return x.cost<y.cost;
}

int t[200005], r[200005];

void unire(int x, int y)
{
if (r[x]>r[y])
    t[y]=x;
else
    {
    if (r[x]<r[y])
        t[x]=y;
    else
        {
        t[y]=x;
        r[x]++;
        }
    }
}

int findu(int x)
{
int temp, rad;
rad=x;

while (t[rad]!=0)
    rad=t[rad];
while (t[x]!=0)
    {
    temp=t[x];
    t[x]=rad;
    x=temp;
    }
return rad;
}

int n, nrm, x, y, cost, rad1, rad2;

int main()
{
    cin>>n>>nrm;
    long long cost_total=0;

    for (int i=1; i<=nrm; i++)
        {
        cin>>x>>y>>cost;
        m.push_back({x, y, cost});
        }

    sort(m.begin(), m.end(), cmp);

    int j=0, nr=1;
    while (nr<n && j<nrm)
        {
        rad1=findu(m[j].x);
        rad2=findu(m[j].y);
        if (rad1!=rad2)
            {
            cost_total+=m[j].cost;
            apm.push_back(m[j]);
            unire(rad1, rad2);
            nr++;
            }
        j++;
        }

    cout<<cost_total<<'\n';
    cout<<apm.size()<<'\n';
    for (auto i:apm)
        cout<<i.y<<' '<<i.x<<'\n';
}