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

using namespace std;

vector <pair<int,int> > v[200001];

pair<int,int> gr[200000];

const int inf= 1 << 30;

int viz[200001],nod,n,s;

void apm()
{
    int i,k=1;

    fill(viz+1,viz+n+1,0);

    priority_queue< pair< int, pair <int, int> >, vector < pair< int, pair< int, int> > >, greater< pair< int, pair< int, int> > > > q;
    q.push(make_pair(0,make_pair(1,1)));
    viz[1]=1;
    while(k<n)
    {
        nod=q.top().second.second;
        q.pop();

        for(i=0;i<v[nod].size();i++)
            if(viz[v[nod][i].first]==0) q.push(make_pair(v[nod][i].second, make_pair(nod,v[nod][i].first)));
        if(viz[q.top().second.second]==0)
        {
            gr[k].first=q.top().second.first;
            gr[k].second=q.top().second.second;
            viz[q.top().second.second]=1;
            s=s+q.top().first;
            k++;
        }
    }


}

int main()
{
    int m,a,b,c,i;

    ifstream mama("apm.in");
    ofstream tata("apm.out");

    mama>>n>>m;
    for(i=0;i<m;i++)
    {
        mama>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    apm();
    tata<<s<<'\n';
    tata<<n-1<<'\n';
    for(i=1;i<n;i++)
        tata<<gr[i].first<<" "<<gr[i].second<<'\n';
    return 0;
}