#include <fstream>
#include <vector>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<int>distMin,nodMin;
vector<bool>folosit;
vector<pair<int,int>>rasp;
vector<vector<pair<int,int>>>gr;
const int inf=1001;
int main(){
    int n,m,nod1,nod2,minn,nod_curent,cost;
    cin>>n>>m;
    distMin.resize(n+1,inf);
    folosit.resize(n+1,false);
    nodMin.resize(n+1,0);
    gr.resize(n+1);
    for(int i=1;i<=m;i++){
        cin>>nod1>>nod2>>cost;
        gr[nod1].push_back({nod2,cost});
        gr[nod2].push_back({nod1,cost});
    }
    folosit[1]=true;
   
    for(int i=0;i<gr[1].size();i++){
        if(gr[1][i].second<distMin[gr[1][i].first]){
            distMin[gr[1][i].first]=gr[1][i].second;
            nodMin[gr[1][i].first]=1;
        }
    }
    cost=0;
     for(int i=1;i<n;i++){
        minn=inf;
        nod_curent=-1;

        for(int j=1;j<=n;j++){
            if(folosit[j]){
                continue;
            }
            if(distMin[j]<minn){
                nod_curent=j;
                minn=distMin[j];
            }   
        }
        folosit[nod_curent]=true; 
        cost+=minn;
        rasp.push_back({nodMin[nod_curent],nod_curent});
    
        for(int j=0;j<gr[nod_curent].size();j++){
            if(folosit[gr[nod_curent][j].first]){
                continue;
            }
            if(gr[nod_curent][j].second<distMin[gr[nod_curent][j].first]){
                distMin[gr[nod_curent][j].first]=gr[nod_curent][j].second;
                nodMin[gr[nod_curent][j].first]=nod_curent;
            }
        }
    }
    cout<<cost<<'\n';
    cout<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
    
}