#include<bits/stdc++.h>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct CustomCompare{
    bool operator()(const vector<int> &a, const vector<int> &b){
        return a[2]>b[2];
    }
};
 bool cmp(vector<int> a, vector<int> b){
    return a[2]<b[2];
}
vector<pair<int,int>> adjList[200001];
vector<int> isInApm;
priority_queue<vector<int>,vector<vector<int>>,CustomCompare>heap;
int cost=0;
vector<pair<int,int>> muchii;


void Prim(int x){
    isInApm[x]++;
    int i;
    for(i=0;i<adjList[x].size();++i){
        if(isInApm[adjList[x][i].first]==0){
            vector<int> aux;
            aux.push_back(x);
            aux.push_back(adjList[x][i].first);
            aux.push_back(adjList[x][i].second);
            heap.push(aux);
            aux.clear();
        }
    }
    vector<int> first;
    while(heap.size()>0){
        first=heap.top();
        heap.pop();
        if(isInApm[first[0]]==1 && isInApm[first[1]]==0){
            muchii.push_back(make_pair(first[0],first[1]));
            cost=cost+first[2];
            Prim(first[1]);
        }
            
        else if(isInApm[first[0]]==0 && isInApm[first[1]]==1){
            muchii.push_back(make_pair(first[0],first[1]));
            cost=cost+first[2];
            Prim(first[0]);
        }
            
        
    }
    
}

int main(){
    int n,m,i,a,b,c;
    f>>n>>m;
    for(i=0;i<n;++i)
        isInApm.push_back(0);
    
    for(i=0;i<m;++i){
        f>>a>>b>>c;
        adjList[a-1].push_back(make_pair(b-1,c));
        adjList[b-1].push_back(make_pair(a-1,c));
    }

    Prim(0);
    
    g<<cost<<'\n';
    g<<muchii.size()<<'\n';

    for(i=0;i<muchii.size();++i){
        g<<muchii[i].first+1<<' '<<muchii[i].second+1<<'\n';
    }
    return 0;
}