#include <bits/stdc++.h>
#define DAU ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define PLEC return 0;

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
#define cin fin
#define cout fout

#define inf 0x3f3f3f3f
#define N 256005

int r[N], n, m, suma, x, y, cost;
vector< pair<int, int> > ales;
vector< pair<int, pair<int, int> > > muchie;

int caut(int poz)
{
    if(r[poz] != poz)r[poz] = caut(r[poz]);
    return r[poz];
}
int unire(int poz1, int poz2)
{
    int t1 = caut(poz1),
        t2 = caut(poz2);
    if(t1 != t2)
    {
        r[t1] = t2;
    }
}

int main()
{
    DAU
    cin >> n >> m;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> cost;
        muchie.push_back({cost,{x,y}});
    }
    sort(muchie.begin(),muchie.end());
    for(int i = 1 ; i <= n ; i++)r[i] = i;
    for(int i = 0 ; i < m ; i++)
    {
        int rx = caut(muchie[i].second.first),
            ry = caut(muchie[i].second.second);
        if(rx != ry)
        {
            unire(rx,ry);
            suma += muchie[i].first;
            ales.push_back({muchie[i].second.first,muchie[i].second.second});
        }
    }
    cout << suma << '\n' << ales.size() << '\n';
    for(int i = 0 ; i < ales.size() ; i++)
    {
        cout << ales[i].first << " " << ales[i].second << '\n';
    }
    PLEC
}