#include<vector>
#include<fstream>
#include<queue>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

typedef pair<int,pair<int,int>> iPPair;

int n, m, mincost, cnt;
vector<iPPair>*G;
vector<bool> V;
vector<pair<int,int>> Ans;
priority_queue<iPPair, vector<iPPair>, greater<iPPair>> Q;



void print(){
    cout << mincost << '\n'
         << Ans.size() << '\n';
    for (auto i:Ans)
        cout << i.first << ' ' << i.second << '\n';
}

void read(){
    cin >> n >> m;
    G = new vector<iPPair>[n + 1];
    V = vector<bool>(n + 1, false);
    for (int x, y, w, i = 1; i <= m;i++)
        cin >> x >> y >> w,
        G[x].push_back(make_pair(w, make_pair(y, x))),
        G[y].push_back(make_pair(w, make_pair(x, y)));
}

void addedge(int node){
    V[node] = true;
    for(auto i:G[node])
        if(!V[i.second.first])
            Q.push(i);
}

void prim(int root){
    addedge(root);
    m = n;
    while(!Q.empty()){
        int node = Q.top().second.first;
        int father = Q.top().second.second;
        int weight = Q.top().first;
        Q.pop();
        if(V[node])
            continue;
        mincost += weight;
        Ans.push_back(make_pair(father, node));
        addedge(node);
    }

}

void solve(){
    read();
    prim(1);
    print();
}

int main(){
    solve();
    return 0;
}