#include <bits/stdc++.h>
#define muchie_data pair<int, pair<int, int>>
#define ll long long

//#define fin cin
//#define fout cout

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

multiset <muchie_data> muchii;
bool inapm[200005];
vector <muchie_data> mapm;

/*
Desigur, iată o explicație simplificată a ambelor algoritme:
Algoritmul lui Prim este folosit pentru a găsi arborele parțial de cost minim (APCM) într-un graf conex ponderat. Funcționează astfel:
Începe cu un nod arbitrar și adaugă-l la APCM.
La fiecare pas, alege muchia cu cel mai mic cost care conectează un nod din APCM cu un nod în afara lui și adaugă acea muchie și nodul la APCM.
Repetă pasul 2 până când toate nodurile sunt incluse în APCM[5].

Algoritmul Kruskal, de asemenea, găsește APCM într-un graf conex ponderat, dar abordează problema diferit:
Sortează toate muchiile grafului în ordine crescătoare după cost.
Începe cu o pădure (o colecție de arbori) care inițial conține fiecare nod ca un arbore separat.
Alege muchiile în ordinea sortată și, pentru fiecare muchie, dacă nodurile pe care le conectează sunt în arbori separați, adaugă muchia la pădure, unind cei doi arbori într-unul singur.
Continuă până când toate nodurile sunt conectate într-un singur arbore, care este APCM[1].
Ambele algoritme sunt exemple de algoritmi greedy și sunt eficienți pentru calculul APCM-ului, alegând la fiecare pas o muchie care adaugă cel mai mic cost posibil la arborele în construcție. Diferența principală între ele este că Prim adaugă muchii bazate pe noduri, în timp ce Kruskal adaugă muchii bazate pe muchii, indiferent de poziția lor actuală în graf. În practică, alegerea între Prim și Kruskal poate depinde de structura specifică a grafului și de modul în care datele sunt stocate și procesate.
*/

int in_apm (muchie_data m)
{
    if (inapm[m.second.first]) return m.second.first;
    if (inapm[m.second.second]) return m.second.second;
    return -1;
}
int not_in_apm (muchie_data m)
{
    if (!inapm[m.second.first]) return m.second.first;
    if (!inapm[m.second.second]) return m.second.second;
    return -1;
}
void display_apm(int n)
{
    for (int i=1; i<=n; i++) {
        if (inapm[i])
            cout<<i<<' ';
    }
    cout<<'\n';
}
int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, x, y, c;
    fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>c;
        muchii.insert({c, {x, y}});
    }
    int root=(*muchii.begin()).second.first;
    inapm[root]=1;
    int sum=0;
    //for (muchie_data m : muchii) cout<<m.first<<' '<<m.second.first<<' '<<m.second.second<<endl;
    //cout<<endl;
    while (!muchii.empty()) {
        for (auto it=muchii.begin(); it!=muchii.end(); it++) {
            auto m=*it;
            //cout<<m.first<<' '<<m.second.first<<' '<<m.second.second<<endl;
            if (in_apm(m)!=-1&&not_in_apm(m)!=-1&&in_apm(m)!=not_in_apm(m)) {
                //cout<<"----"<<m.first<<' '<<m.second.first<<' '<<m.second.second<<endl;
                int napm=not_in_apm(m);
                inapm[napm]=1;
                mapm.push_back(m);
                sum+=m.first;
                muchii.erase(it);
                break;
            }
            else if (not_in_apm(m)==-1) {
                it=muchii.erase(it);
                if (it==muchii.end()) break;
                it--; 
                //Without this, the it++ in for would jump over a element because it=muchii.erase(it) is already the next one
            }
        }
        //display_apm(n);
    }
    fout<<sum<<'\n'<<mapm.size()<<'\n';
    for (muchie_data m : mapm) {
        fout<<m.second.first<<' '<<m.second.second<<'\n';
    }
    return 0;
}