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

using namespace std;
ifstream intrare("apm.in");
ofstream iesire("apm.out");
const int inf=(1<<28);
const int NMAX=200005;
int n,m,i,j,tata[NMAX];
bool vizitat[NMAX];
int dmin[NMAX];


struct comparator{

bool operator()(int x,int y){
return dmin[x]>dmin[y];
}


};
vector < pair < int, int > >graf[NMAX];
priority_queue < int, vector < int >, comparator >q;
int costt;

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

    q.push(1);
    //vizitat[1]=1;
    for(int i=1;i<=n;i++)
        dmin[i]=inf;

    dmin[1]=0;

    while(!q.empty()){

        int nod=q.top();
        q.pop();
        if(!vizitat[nod]){

 costt+=dmin[nod];
 //cout<<dmin[nod]<<" "<<nod<<endl;
        vizitat[nod]=1;
        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] && cost<dmin[vecin]){
                dmin[vecin]=cost;

                q.push(vecin);

                tata[vecin]=nod;
            }
        }
        }

    }
iesire<<costt<<endl;
iesire<<n-1<<endl;
for(int i=1;i<=n;i++)
    iesire<<i<<" "<<tata[i]<<endl;


    return 0;
}