#include <stdio.h>
#include <iostream>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <string.h>

using namespace std;

#define COSTMAX 1001

struct Node {
    int v;
    int cost;
    Node(int u, int c) : v(u), cost(c) {}
};

struct LessNode {

    bool operator()(const Node& lhs, const Node& rhs) const {
        if (lhs.cost == rhs.cost) {
            return lhs.v < rhs.v;
        }
        return lhs.cost < rhs.cost;
    }
};

map<int, vector<Node> > graph;
set<Node, LessNode> pq;
vector<int> dist;
vector<int> parent; 

int primMST(int N) {
    bool vis[N + 1];
    memset(vis, false, sizeof (vis));
    int MST = 0;
    while (!pq.empty()) {
        Node minCost = *(pq.begin());
        MST += minCost.cost;
        vis[minCost.v] = true;
        vector<Node> neighbours = graph[minCost.v];
        for (int i = 0; i < neighbours.size(); i++) {
            Node curr = neighbours[i];
            if (!vis[curr.v]) {
                if (dist[curr.v] > curr.cost) {
                    set<Node>::iterator it = pq.find(Node(curr.v, dist[curr.v]));
                    pq.erase(it);
                    dist[curr.v] = curr.cost;
                    pq.insert(Node(curr.v, curr.cost));
                    parent[curr.v] = minCost.v;
                }
            }
        }
        pq.erase(minCost);
    }
    return MST;
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        Node n(v, c);
        graph[u].push_back(n);
        graph[v].push_back(Node(u, c));
    }

    pq.insert(Node(1, 0));
    dist.push_back(0);
    dist.push_back(0); 
    parent.push_back(-1); 
    parent.push_back(-1); 

    for (int i = 2; i <= N; i++) {
        pq.insert(Node(i, COSTMAX));
        dist.push_back(COSTMAX);
        parent.push_back(-1); 
    }
    
    int minSum = primMST(N); 
    cout << minSum << endl;
    cout << N - 1 << endl;
    for (int i = 1; i <= N; i++) {
        if (parent[i] != -1) {
            cout << i << " " << parent[i] << endl ;
        }
    }

    fclose(stdout);

}