#include<vector>
#include<fstream>
#include<queue>
#include<algorithm>
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<int> Rang;
vector<int> T;
vector<pair<int,int>> Ans;



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

void read(){
    cin >> n >> m;
    T = vector<int>(n + 1);
    Rang = vector<int>(n + 1, 1);
    for (int x, y, w, i = 1; i <= m;i++)
        cin >> x >> y >> w,
        G.push_back(make_pair(w, make_pair(y, x))),
        G.push_back(make_pair(w, make_pair(x, y)));
    sort(G.begin(), G.end());
    for (int i = 1; i <= n;i++)
        T[i] = i;
}

int root(int node){
    while(T[node]!=node)
        node = T[node];
    return node;
}

void Union(int x,int y){
    int a = root(x);
    int b = root(y);
    T[a] = T[b];
}

void kruskal(){
    int node, father, weight;
    for(auto i:G){
        node = i.second.first;
        father = i.second.second;
        weight = i.first;
        if(root(node)!=root(father))
            mincost += weight,
            Ans.push_back(make_pair(node,father)),
            Union(node, father);
    }
}

void solve(){
    read();
    kruskal();
    print();
}

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