#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
vector<int>nodMin,distMin;
vector<bool>folosit;
vector<pair<int,int>>rasp;
vector<vector<pair<int,int>>>gr;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
const int inf=1001;
int main(){
    int n,m,nod1,nod2,minn,nod_curent,cost;
    cin>>n>>m;
    folosit.resize(n+1,false);
    nodMin.resize(n+1,0);
    distMin.resize(n+1,inf);
    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++){
       q.push({gr[1][i].second,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;

        while(nod_curent==-1){
            if(!folosit[q.top().second]){
                nod_curent=q.top().second;
                minn=q.top().first;
            }
             q.pop();
        }
        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]){
                  nodMin[gr[nod_curent][j].first]=nod_curent;
                  distMin[gr[nod_curent][j].first]=gr[nod_curent][j].second;
                q.push({gr[nod_curent][j].second,gr[nod_curent][j].first});
            }
        }
    }
    cout<<cost<<'\n';
    cout<<rasp.size()<<'\n';
    for(int i=0;i<rasp.size();i++){
        cout<<rasp[i].first<<" "<<rasp[i].second<<'\n';
    }
    
}