#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <chrono>
#include <numeric>

#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>  
#include <stack>
#include <queue>
#include <list>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
 
double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);

#define M 1000000007

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

template<class T> T nxt() {
    T x;
    cin >> x;
    return x;
}

struct Tree{
    int root,height;
    Tree(){
        this->root=0;
        this->height=0;
    }
    Tree(int _root,int _height){
        this->root=_root;
        this->height=_height;
    }
};

vector<Tree> createForest(const int& noNodes){
    vector<Tree> forest(noNodes+1);
    for(int i=1;i<=noNodes;++i){
        forest[i]=Tree(i,0);
    }
    return forest;
}

// Find the root of the tree where this node belongs
// Uses Road Compression Heuristic
int getTreeRootOf(vector<Tree>& forest,const int& node){
    if(node<1||node>int(forest.size())-1){
        cout<<"Node doesn't exist in the forest!";
        exit(1);
    }

    stack<int> visitedNodes;
    int currentNode=node,nodeRoot;
    while(currentNode!=forest[currentNode].root){
        visitedNodes.push(currentNode);
        currentNode=forest[currentNode].root;
    }
    nodeRoot=currentNode;

    while(visitedNodes.size()){
        int x=visitedNodes.top();
        forest[x].root=nodeRoot;
        visitedNodes.pop();
    }

    return currentNode;
}

// Combines the trees where the 2 nodes belonds
// Assumes the 2 nodes DON'T belong to the same tree,otherwise does nothing
// Uses Height Reuninion(Reuniunea dupa rang ( ͡° ͜ʖ ͡°))
void combineTreesOf(vector<Tree>& forest,const int& node1,const int& node2){
    int height,rootNode1=getTreeRootOf(forest,node1),rootNode2=getTreeRootOf(forest,node2);

    if(rootNode1!=rootNode2){
        if(forest[rootNode1].height<forest[rootNode2].height){
            height=max(forest[rootNode1].height+1,forest[rootNode2].height);
            
            forest[rootNode1].root=rootNode2;
            forest[rootNode2].height=height;
        }
        else{
            height=max(forest[rootNode1].height,forest[rootNode2].height+1);
            
            forest[rootNode2].root=rootNode1;
            forest[rootNode1].height=height;
        }
    }
}

struct Edge{
    int node1,node2;
    ll cost;
    Edge(int _node1,int _node2,ll _cost){
        this->node1=_node1;
        this->node2=_node2;
        this->cost=_cost;
    }
};

bool Compare(const Edge& a,const Edge& b){
    return a.cost<b.cost;
}

// Kruskals Algorithm
// O(Mlog*N + Mlog2M)
pair<ll,vector<Edge>> getMinimumSpanningTree(const int& noNodes,vector<Edge> edges){
    sort(all(edges),Compare);

    ll totalCost=0;
    vector<Edge> treeEdges;

    vector<Tree> forest=createForest(noNodes);

    for(int i=0;i<edges.size();++i){
        auto edge=edges[i];
        int root1=getTreeRootOf(forest,edge.node1),root2=getTreeRootOf(forest,edge.node2);
        if(root1!=root2){
            totalCost+=edge.cost;
            treeEdges.push_back(edge);
            combineTreesOf(forest,edge.node1,edge.node2);
        }
    }

    return {totalCost,treeEdges};
}

void Solve(){
    int n,m;
    fin>>n>>m;
    vector<Edge> edges;
    for(int i=0;i<m;++i){
        int x,y;
        ll c;
        fin>>x>>y>>c;
        edges.push_back(Edge(x,y,c));
    }

    ll totalCost;
    vector<Edge> treeEdges;
    tie(totalCost,treeEdges)=getMinimumSpanningTree(n,edges);

    fout<<totalCost<<'\n'<<n-1<<'\n';
    for(auto edge:treeEdges){
        fout<<edge.node1<<' '<<edge.node2<<'\n';
    }
}

int main(){
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);

    // ios_base::sync_with_stdio(false);
    // cin.tie(NULL);

    // std::string file="FILE";
    // std::ifstream in(file+".in");
    // std::streambuf *finbuf = std::fin.rdbuf(); //save old buf
    // fin.rdbuf(in.rdbuf()); //redirect std::fin
    
    // std::ofstream out(file+".out");
    // std::streambuf *foutbuf = std::fout.rdbuf(); //save old buf
    // fout.rdbuf(out.rdbuf()); //redirect std::fout
	
    Solve();

    // std::fin.rdbuf(finbuf);   //reset to standard input again
    // std::fout.rdbuf(foutbuf); //reset to standard output again

    return 0;
}