#include <bits/stdc++.h>

using namespace std;

const int nmax=200005;

vector <pair <int, pair <int, int> > > v;
vector <pair <int, int> > rasp;
int tata[nmax];

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

int tata_suprem(int i)
{
    if(tata[i]==i)
        return i;
    return tata[i]=tata_suprem(tata[i]);
}

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

    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        pair < int, pair <int, int> > muchie;
        muchie.first=c;
        muchie.second.first=a;
        muchie.second.second=b;
        v.push_back(muchie);
    }
    sort(v.begin(), v.end(), cmp);
    for(int i=1;i<=n;i++)
        tata[i]=i;
    int curent=0;
    int s=0;
    for(int cnt=0;cnt<n-1;curent++)
    {
        int x, y;
        x=v[curent].second.first;
        y=v[curent].second.second;
        if(tata_suprem(x)!=tata_suprem(y))
        {
            s+=v[curent].first;
            tata[tata_suprem(y)]=tata_suprem(x);
            cnt++;
            rasp.push_back(make_pair(x, y));
        }
    }
    printf("%d\n", s);
    printf("%d\n", n-1);
    for(int i=0;i<n-1;i++)
        printf("%d %d\n", rasp[i].first, rasp[i].second);

    return 0;
}