#include <fstream>
#include <queue>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
const int N = 102, INF = ((1<<31)-1);
vector<pair<int, int> > V[N];
int n, m;
void Prim(){
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > Q;
    int src = 1;
    vector<int> key(N, INF);
    vector<int> P(N, -1);
    vector<bool> Include(N, false);
    Q.push({1, src});
    while(!Q.empty()){
        int u = Q.top().second;
        Q.pop();
        if(Include[u])
            continue;
        Include[u] = true;
        for(vector<pair<int, int> >::iterator it = V[u].begin(); it != V[u].end(); it++){
            int v = (*it).first, w = (*it).second;
            if(Include[v] == false && key[v] > w){
                key[v] = w, P[v] = u;
                Q.push({key[v], v});
            }
        }
    }
    int SArbore = 0;
    for(int i=2; i<=n; i++){
        int r = 0;
        for(int j=0; j<V[P[i]].size(); j++){
            if(V[P[i]][j].first == i){
                r = V[P[i]][j].second;
            }
        }
        SArbore += r;
    }
    cout << SArbore << '\n' << n-1 << '\n';
    for(int i=2; i<=n; i++)
        cout << P[i] << ' ' << i << '\n';
}
int main()
{
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int x1, x2, c;
        cin >> x1 >> x2 >> c;
        V[x1].push_back({x2, c});
        V[x2].push_back({x1, c});
    }
    Prim();
    return 0;
}