#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <string>
#include <sstream>
using namespace std;

string IntToString (int a)
{
    ostringstream temp;
    temp<<a;
    return temp.str();
}
struct muchie
{
    int a,b,c;
    muchie(int aa, int bb, int cc)
    {
        a=aa;b=bb;c=cc;
    }
};

int main()
{
    int i,ii,n,muchii_nr;
    ifstream istr("apm.in");
    istr >> n;
    istr >> muchii_nr;

    vector<muchie> muchii;

    for (i=0;i<muchii_nr;i++)
    {
        int a,b,c;
        istr >>a;
        istr >>b;
        istr >>c;
        a--;b--;

        muchii.push_back(muchie(a,b,c));
    }
    set<int> marked;
    int n2=n; int sum=0;
    marked.insert(0);
    
    ofstream ostr("apm.out");
    string g ="";
    while (n2>1)
    {
        int min=9999; vector<muchie>::iterator it_min;
        for(vector<muchie>::iterator it = muchii.begin(); it != muchii.end(); ++it)
        {
            if (it->c < min)
            {
                if ((marked.find(it->a) != marked.end()) != (marked.find(it->b) != marked.end()))
                {
                    min = it->c;
                    it_min = it;
                }
            }
        }
        marked.insert(it_min->a);
        marked.insert(it_min->b);
        
        g+=IntToString(it_min->a+1);
        g+=" ";
        g+=IntToString(it_min->b+1);
        g+="\n";
        
        //cout <<"(" << (it_min->a)+1 << ", " << it_min->b+1 << ": " << it_min->c <<") ";
        //cout <<"==";
        //cout <<"(" << (char)((it_min->a)+'A') << ", " << (char)(it_min->b+'A') << ": " << it_min->c <<") \n";
        --n2;
        sum+=it_min->c;
    }
    ostr << sum << "\n" << n-1 << "\n" << g;
    cout << "\n\nSUM: " << sum;
    istr.close();
    ostr.close();
    cin >>i;;
    
    return 0;
}