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

using namespace std;

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

struct muchie
{
    int x,y;
    int cost;
}v[100000];

int t[100000],rang[100000];
vector<pair <int, int> >a;

bool compare(muchie a, muchie b)
{
    return a.cost<b.cost;
}

int aia(int x)
{
    int s=x;
    while(t[s]!=s)
        s=t[s];
    while(t[x]!=x)
    {
        int y=t[x];
        t[x]=s;
        x=y;
    }
    return s;
}

void merge1(int a, int b)
{
    if(rang[a]>rang[b])
        t[b]=a;
    else
        t[a]=b;
    if(rang[a]==rang[b])
        rang[b]++;
}

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(aia(v[i].x)!=aia(v[i].y))
        {
            merge1(aia(v[i].x), aia(v[i].y));
            cost=cost+v[i].cost;
            a.push_back({v[i].y, v[i].x});
        }
    }
    g<<cost<<'\n'<<a.size()<<'\n';

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

    return 0;
}