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

using namespace std;

vector < pair <int,int> > v[200001];
priority_queue < pair <int,pair<int,int> >, vector < pair<int,pair<int,int> > >, greater <pair<int,pair<int,int> > > > q;

int n,m,nrm,vizitat[200001],suma,vx[200001],vy[200001];

void apm()
{
    int a,b,k,ok;
    vizitat[1]=1;
    while(nrm<=n-1 && !q.empty())
    {
        b=q.top().second.second;
        a=q.top().second.first;

        ok=1;
        if(vizitat[b]==0)
        {
            suma+=q.top().first;
            vizitat[b]=1;
            ok=0;
            vx[nrm]=a;
            vy[nrm]=b;
            nrm++;
            q.pop();
            for(k=0; k<v[b].size(); k++)
            {
                if(vizitat[v[b][k].first]==0)
                q.push(make_pair(v[b][k].second, make_pair (b, v[b][k].first)));
            }

        }
        if(vizitat[b]==1 && ok==1)
            q.pop();
    }
}

int main()
{
    int i,j,x,y,c;
    ifstream in("apm.in");
    in>>n>>m;
    for(i=0; i<m; i++)
    {
        in>>x>>y>>c;
        v[x].push_back(make_pair(y,c));
        v[y].push_back(make_pair(x,c));
    }
    for(i=0; i<v[1].size(); i++)
        q.push(make_pair(v[1][i].second,make_pair(1, v[1][i].first)));
    apm();
    ofstream out("apm.out");
    out<<suma<<endl;
    out<<n-1<<endl;
    for(i=0; i<n-1; i++)
        out<<vx[i]<<" "<<vy[i]<<endl;
    in.close();
    out.close();
    return 0;
}