#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>



using namespace std;

ifstream f("APM.in");
ofstream g("APM.out");

struct M
{
    int x,y;
    int cost;
}v[400000];

int t[200000],rang[200000];
vector<pair <int, int> >x;

bool compare(M x, M y)
{
    return x.cost<y.cost;
}

int A(int x)
{
    int w=x;
    while(t[w]!=w)
        w=t[w];
    while(t[x]!=x)
    {
        int y=t[x];
        t[x]=w;
        x=y;
    }
    return w;
}

void RANG_(int x, int y)
{
    if(rang[x]>rang[y])
        t[y]=x;
    else
        t[x]=y;
    if(rang[x]==rang[y])
        rang[y]++;
}

int main()
{
    int n,m;
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].cost;

    sort(v+1,v+m+1,compare);


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

    int cost=0;
    for(int i=1;i<=m;i++)
    {
        if(A(v[i].x)!=A(v[i].y))
        {
            RANG_(A(v[i].x), A(v[i].y));
            cost=cost+v[i].cost;
            x.push_back({v[i].y, v[i].x});
        }
    }
    g<<cost<<'\n'<<x.size()<<'\n';

    for(int i=0;i<x.size();i++)
        g<<x[i].first<<" "<<x[i].second<<'\n';

    return 0;
}