#include <bits/stdc++.h>
using namespace std;
int n, m;

vector<vector<pair<int, int> > >graph;

vector<int> key;
vector<bool> inTree;
vector<int> father;

int minKeyIndex(){
    int minKey = INT_MAX, minIndex;
    for(auto i=1; i<=n; i++){
        if(inTree.at(i)==false && key.at(i)<minKey){
            minKey = key.at(i);
            minIndex = i;
        }
    }

    return minIndex;
}

int main()
{
    ifstream fin("apm.in");
    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));
    }

    father.resize(n+1);
    key.resize(n+1, INT_MAX);
    inTree.resize(n+1, false);
    key.at(1)=0;

    for(auto i=1; i<n; i++){

        int minIndex = minKeyIndex();
        inTree.at(minIndex) = true;

        for(auto& neighbour:graph.at(minIndex)){
            if(inTree.at(neighbour.first)==false && (key.at(neighbour.first)>neighbour.second))
                key.at(neighbour.first) = neighbour.second, father.at(neighbour.first) = minIndex;
        }
    }
    ofstream fout("apm.out");

    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<<" "<<father.at(i)<<endl;

}