#include <iostream>
#include <fstream>
#include <vector>
#include <functional>
#include <queue>
using namespace std;
ifstream intrare("apm.in");
ofstream iesire("apm.out");
const int NMAX=200005;
vector < pair < int, int > > graf[NMAX];
int distmin[NMAX];

struct compara{

bool operator()(int x,int y){

return distmin[x]>distmin[y];
}


};





priority_queue < int ,vector < int >, compara >q;
const int inf=(1<<28);
int i,j,n,m,tata[NMAX];
long int costtotal=0;
bool vizitat[NMAX];


void prim(int nod){

q.push(nod);

while(!q.empty()){

    int nod=q.top();
vizitat[nod]=true;

    q.pop();

    for(size_t i=0;i<graf[nod].size();i++){
        int vecin=graf[nod][i].first;
        int cost=graf[nod][i].second;

            if(!vizitat[vecin])
            {
            if(cost<distmin[vecin]){
                distmin[vecin]=cost;
                    tata[vecin]=nod;
                    q.push(vecin);

                }




        }
    }


}


}



int main()
{
intrare>>n>>m;
for(int i=1;i<=m;i++)
{
    int x,y,c;
    intrare>>x>>y>>c;
    graf[x].push_back(make_pair(y,c));
    graf[y].push_back(make_pair(x,c));

}

for(int i=1;i<=n;i++)
    distmin[i]=inf;

distmin[1]=0;


prim(1);
for(int i=1;i<=n;i++)
    costtotal+=distmin[i];
iesire<<costtotal;
iesire<<endl;
iesire<<n-1<<endl;
for(int i=2;i<=n;i++)
iesire<<i<<" "<<tata[i]<<endl;


    return 0;
}