#include<fstream>
#include<vector>
#include<queue>
#include<utility>

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

const int oo=1000000000,Nmax=200000;
struct muchie
{
    int x,y,cost;
    bool operator < (const muchie &janis) const
    {
        return cost>janis.cost;
    }
};
vector<muchie> v[Nmax],sol;
int n,m,k,S;
int viz[Nmax];
priority_queue<muchie> Q;

void citire()
{
    fin>>n>>m;
    muchie aux;
    for(int i=0; i<m; i++)
    {
        fin>>aux.x>>aux.y>>aux.cost;
        v[aux.x].push_back(aux);
        swap(aux.x,aux.y);
        v[aux.x].push_back(aux);
    }
}

void Prim()
{
    muchie aux;

    for(int i=0;i<v[1].size();i++)
        Q.push(v[1][i]);
    viz[1]=1;

    while(!Q.empty()&&k<n-1)
    {
        aux=Q.top();
        Q.pop();

        if(!viz[aux.y])
        {
            viz[aux.y]=1;
            k++;
            S+=aux.cost;
            sol.push_back(aux);
            for(int i=0;i<v[aux.y].size();i++)
                if(!viz[v[aux.y][i].y])
                    Q.push(v[aux.y][i]);
        }
    }
}

void afis()
{
    fout<<S<<'\n';
    fout<<k<<'\n';
    for(int i=0;i<sol.size();i++)
        fout<<sol[i].x<<' '<<sol[i].y<<endl;
}

int main()
{
    citire();
    Prim();
    afis();


    fin.close();
    fout.close();
    return 0;
}