#include <iostream>
#include <fstream>
#include <vector>
#define nmax 200003
#define inf 1e9
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m, viz[nmax], tata[nmax], costtot, nr;
vector < pair<int,int> > v[nmax];

void citire()
{
    int i,j,k,c;
    f>>n>>m;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>c;
        v[i].push_back({j,c});
        v[j].push_back({i,c});
    }
}

void prim()
{
    int i,j,k,mn, S, D;
    for(i=1; i<=n; i++)
    {
        viz[i]=0;
        tata[i]=0;
    }
    costtot=0;
    viz[1]=1;
    for(k=1; k<=n-1; k++)
    {
        mn=inf;
        for(i=1; i<=n; i++)
        for(j=0; j<v[i].size(); j++)
            if((viz[i]==1 && viz[v[i][j].first]==0) && mn>v[i][j].second)
        {
            mn=v[i][j].second;
            S=i;
            D=v[i][j].first;
        }
        viz[D]=1;
        tata[D]=S;
        //cout<<S<<"-"<<D<<endl;
        costtot+=mn;
        nr++;
    }
    /*cout<<"Arborele: "<<endl;
    for(i=1; i<=n; i++)
        cout<<tata[i]<<" ";
    cout<<endl;*/
}

int main()
{
    int i;
    citire();
    prim();
    g<<costtot<<"\n";
    g<<nr<<endl;
    for(i=1; i<=n; i++)
        if(tata[i])
        g<<i<<" "<<tata[i]<<endl;
    f.close();
    g.close();
    return 0;
}