#include <vector>

#include <fstream>

#include <utility>
using namespace std;
class graf
{
    int n;
    int m;
    vector<vector<pair<int,int>>>gr;
public:
    graf()
    {
        ifstream citire("apm.in");
        citire>>n;
        citire>>m;
        gr.resize(n+1);

        for(int i=0;i<m;i++)
        {
            pair<int,int>temp;
            pair<int,int>temp2;
            int j;
            citire>>j>>temp.first>>temp.second;
            temp2.first=j;
            temp2.second=temp.second;
            gr[temp.first].push_back(temp2);
            gr[j].push_back(temp);
        }
        citire.close();
    }
    void prim()
    {
        vector<int>varfuri(n+1,0);
        vector<pair<int,int>>muchii;
        varfuri[1]=1;
        int suma=0;
        int noduri_adaugate=1;
        while(noduri_adaugate<n)
        {
            vector<int>minim(n+1,999);
            int i_min=999;
            pair<int,int>nod_minim;
            nod_minim.first=nod_minim.second=999;
            for(int i=1;i<varfuri.size();i++)
            {
                if(varfuri[i]==1)
                {
                        for(pair<int,int> y:gr[i])
                        {
                            if(y.second<minim[y.first] && varfuri[y.first]==0)
                            {
                                minim[y.first]=y.second;
                                if(y.second<nod_minim.second)
                                {
                                    i_min=i;
                                    nod_minim.second=y.second;
                                    nod_minim.first=y.first;
                                }
                            }
                        }
                }

            }
            muchii.push_back(make_pair(i_min,nod_minim.first));
            varfuri[nod_minim.first]=1;

            suma+=nod_minim.second;
            noduri_adaugate++;
        }
        ofstream scriere("apm.out");
        scriere<<suma<<"\n";
        scriere<<muchii.size()<<"\n";
        for(pair<int,int> &x:muchii)
            scriere<<x.second<<" "<<x.first<<"\n";
        scriere.close();
    }
};
int main()
{
    graf test;
    test.prim();
    return 0;
}