#include <bits/stdc++.h>
using namespace std;

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;
vector<vector<pair<int, int> > > graph;
vector<bool> inTree;
vector<int> key;
vector<int> parent;
int n, m;

void apm(int source){
    inTree.resize(n+1, false);
    key.resize(n+1, INT_MAX);
    parent.resize(n+1, -1);

    key.at(source) = 0;

    heap.push(make_pair(0, source));

    while(!heap.empty()){
        int currentNode = heap.top().second;
        inTree.at(currentNode) = true;
        heap.pop();

        for(auto& node:graph.at(currentNode)){
            if(inTree.at(node.first)==false && key.at(node.first)>node.second){
                key.at(node.first) = node.second;
                heap.push(make_pair(key.at(node.first), node.first));
                parent.at(node.first) = currentNode;
            }
        }
    }
}


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

    fin>>n>>m;

    graph.resize(n+1, vector<pair<int, int> > ());

    int x, y, c;
    for(auto i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
        graph.at(y).push_back(make_pair(x, c));
    }

    apm(1);

    long long cost = 0;
    for(auto i=2; i<=n; i++) cost+=key.at(i);

    fout<<cost<<endl<<n-1<<endl;

    for(auto i=2; i<=n; i++) fout<<i<<" "<<parent.at(i)<<endl;
}