#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))),
    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){
    if(Rang[x]<Rang[y])
        T[x] = y;
    else if(Rang[y]>Rang[x])
        T[y] = x;
    else
        T[x] = y,
        Rang[y]++;
}

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

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

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