#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

int n, m;

const int nmax=400005;
const int lim=200005;

vector < pair <int, pair <int, int> > > muchii;
vector < pair <int, pair <int, int> > > util_stiva;
stack <pair <int, pair <int, int> > > stiva;
int sef[lim];

void add(int a, int b)
{
    while(sef[a]!=0)
        a=sef[a];
    sef[b]=a;
}
bool verif(int a, int b)
{
    while(sef[a]!=0)
        a=sef[a];
    while(sef[b]!=0)
        b=sef[b];
    if(a==b)
        return true;
    return false;
}

bool verif_conex()
{
    int s=muchii.size();
    for(int i=0;i<s;i++)
        add(muchii[i].second.first, muchii[i].second.second);
    s=util_stiva.size();
    for(int i=0;i<s;i++)
        add(util_stiva[i].second.first, util_stiva[i].second.second);
    int ult_sef=sef[1];
    if(ult_sef==0)
        ult_sef=1;
    int cnt0=0;
    for(int i=2;i<=n;i++)
    {
        if(sef[i]==0)
        {
            cnt0++;
            continue;
        }
        if(cnt0>1)
            return false;
        if(verif(ult_sef, i)==false)
            return false;
    }
    return true;
}

bool cmp(pair <int, pair <int, int> > a, pair <int, pair <int, int> > b)
{
    return a.first<b.first;
}

int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d%d", &n, &m);
    int suma=0;
    for(int i=1;i<=m;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        muchii.push_back(make_pair(c, make_pair(a, b)));
        suma+=c;
    }
    sort(muchii.begin(), muchii.end(), cmp);
    while(muchii.size()+stiva.size()>n-1&&muchii.size()>0)
    {
        stiva.push(muchii.back());
        util_stiva.push_back(muchii.back());
        muchii.pop_back();
        suma-=stiva.top().first;
        if(verif_conex()==false)
            suma+=stiva.top().first;
        else
        {
            stiva.pop();
            util_stiva.pop_back();
        }
        memset(sef, 0, sizeof(sef));
    }
    printf("%d\n", suma);
    printf("%d\n", n-1);
    for(int i=0;i<muchii.size();i++)
        printf("%d %d\n", muchii[i].second.first, muchii[i].second.second);
    while(stiva.size()>0)
    {
        printf("%d %d\n", stiva.top().second.first, stiva.top().second.second);
        stiva.pop();
    }

    return 0;
}