#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <set>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

class Graph {
    protected:
        int n;
        int m;
        int start;
        int c;
        int last;
        int diam;
        static int noBC;
        vector<vector<int>> adjList;
        vector<bool> vis;
        vector<vector<int>> adjListT;
        vector<int> dist;
        vector<int> solComp[100001];
        stack<int> S;
        vector<int> lvl;
        vector<int> low;
        vector<vector<int>> solBC;
        vector<int> subset;
    public:
        Graph() {};
        void directedGraphCTC();
        void dfsBC(int start, int pred);
        int getSolBC();
        void dfsT(int start);
        void printCTC();
        void dijkstra();
        void bellmanford();

        void disjoint();
        void royFloyd();
        void readDarb();
        void bfsDarb(int node);
        void solDarb();
};

class UndirectedGraph : public Graph {
    private:
        int noCompConex;
    public:
        UndirectedGraph(string inPath);
        void dfs(int start);
        int dfsCompConex(string outPath);
};

UndirectedGraph :: UndirectedGraph(string inPath) {
    ifstream in(inPath);

    int n, m;

    in >> n >> m;

    this -> n = n;
    this -> m = m;
    adjList.resize(n + 1);
    vis.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        adjList[x].push_back(y);
        adjList[y].push_back(x);
    }
}

void UndirectedGraph :: dfs(int start) {
    vis[start] = true;

    for (auto x : adjList[start])
        if (!vis[x])
            dfs(x);
}

int UndirectedGraph :: dfsCompConex(string outPath) {
    ofstream out(outPath);

    noCompConex = 0;

    for (int i = 1; i <= n; i++)
        if (!vis[i]) {
            dfs(i);
            noCompConex++;
        }

    out << noCompConex;

    return noCompConex;
}

class DirectedGraph : public Graph {
    private:
        stack<int> topSorted;
    public:
        DirectedGraph(string inPath);
        void bfs(int start);
        vector<int> getBfs(string outPath);
        void dfsTopSort(int start);
        void topSort(string outPath);
};

DirectedGraph :: DirectedGraph(string inPath) {
    ifstream in(inPath);

    int n, m;

    in >> n >> m;

    this -> n = n;
    this -> m = m;
    adjList.resize(n + 1);
    vis.resize(n + 1);
    dist.resize(n + 1, -1);

    for (int i = 0; i < m; i++) {
        int x, y;
        in >> x >> y;
        adjList[x].push_back(y);
    }
}

void DirectedGraph :: bfs(int start) {
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (auto i : adjList[node])
            if (dist[i] == -1) {
                dist[i] = dist[node] + 1;
                q.push(i);
            }
    }
}

vector<int> DirectedGraph :: getBfs(string outPath) {
    ofstream out(outPath);

    for (int i = 1; i <= n; i++)
        out << dist[i] << " ";

    return dist;
}

void DirectedGraph :: dfsTopSort(int start) {
    vis[start] = true;

    for (auto x : adjList[start])
        if (!vis[x])
            dfsTopSort(x);

    topSorted.push(start);
}

void DirectedGraph :: topSort(string outPath) {
    ofstream out(outPath);

    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfsTopSort(i);

    while (!topSorted.empty()) {
        out << topSorted.top() << " ";
        topSorted.pop();
    }
}

class UndirectedWeightedGraph : public Graph {
    private:
        vector<int> subset;
        vector<pair<int, int>> sol;
    public:
        UndirectedWeightedGraph(string inPath);
        struct edge {
            int a, b;
            int w;
            friend bool operator<(const edge& A, const edge& B) {
                return A.w < B.w;
            }
        };
        vector<edge> adjList;
        int findNode(int node);
        void unite(int node1, int node2);
        void apm(string outPath);
};

UndirectedWeightedGraph :: UndirectedWeightedGraph(string inPath) {
    ifstream in("apm.in");

    int n, m;

    in >> n >> m;

    this -> n = n;
    this -> m = m;
    subset.resize(n + 1);

    for (int i = 1; i <= n; i++)
        subset[i] = i;

    for (int i = 1; i <= m; i++) {
        edge X;
        in >> X.a >> X.b >> X.w;
        adjList.push_back(X);
    }
}

int UndirectedWeightedGraph :: findNode(int node) {
    if (node == subset[node])
        return node;

    return subset[node] = findNode(subset[node]);
};

void UndirectedWeightedGraph :: unite(int node1, int node2) {
    int a = findNode(node1);
    int b = findNode(node2);
    subset[b] = a;
}

void UndirectedWeightedGraph :: apm(string outPath) {
    ofstream out(outPath);

    sort(adjList.begin(), adjList.end());

    int s = 0;

    for (auto i : adjList) {
        int a = findNode(i.a);
        int b = findNode(i.b);

        if (a == b)
            continue;
        else {
            unite(i.a, i.b);
            sol.emplace_back(i.a, i.b);
            s += i.w;
        }
    }

    out << s << '\n' << n - 1 << '\n';
    for (auto i : sol)
        out << i.first << " " << i.second << '\n';
}
///////////////////////////////
int Graph :: noBC = 0;

void Graph :: directedGraphCTC() {
    ifstream fin("ctc.in");

    fin >> n >> m;

    adjList.resize(n + 1);
    adjListT.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int x, y;
        fin >> x >> y;
        adjList[x].push_back(y);
        adjListT[y].push_back(x);
    }

    fin.close();
}

void Graph :: dfsBC(int start, int pred) {
    vis[start] = 1;
    S.push(start);
    lvl[start] = low[start] = lvl[pred] + 1;

    for (auto x : adjList[start])
        if (x != pred)
            if (vis[x])
                if (low[start] > lvl[x])
                    low[start] = lvl[x];
            else {
                dfsBC(x, start);

                if (low[start] > low[x])
                    low[start] = low[x];

                if (lvl[start] < low[x]) {
                    noBC++;

                    while (S.top() != x) {
                        solBC[noBC].push_back(S.top());
                        S.pop();
                    }

                    solBC[noBC].push_back(x);
                    S.pop();
                    solBC[noBC].push_back(start);
                }
            }

}

int Graph :: getSolBC() {
    return noBC;
}

void Graph :: dijkstra() {
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    vector<vector<pair<int, int>>> adjList;
    priority_queue <pair<int, int>> q;
    int n, m;

    fin >> n >> m;

    adjList.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        fin >> a >> b >> w;
        adjList[a].push_back(make_pair(b, w));
    }

    vector<int> dist(n + 1, INF);

    dist[1] = 0;
    q.push(make_pair(0, 1));

    while (!q.empty()) {
        int node = q.top().second;

        if (dist[node] != -q.top().first) {
            q.pop();
            continue;
        }

        q.pop();

        for (auto x : adjList[node])
            if (dist[node] + x.second < dist[x.first]) {
                dist[x.first] = dist[node] + x.second;
                q.push(make_pair(-dist[x.first], x.first));
            }
    }

    for (int i = 2; i <= n; i++)
        if (dist[i] != INF)
            fout << dist[i] << " ";
        else
            fout << 0 << " ";
}

void Graph :: bellmanford() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    int n, m;
    vector<vector<pair<int, int>>> adjList;

    fin >> n >> m;

    adjList.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        fin >> a >> b >> w;
        adjList[a].push_back(make_pair(b, w));
    }

    vector<int> dist(n + 1, INF);
    queue<int> q;
    vector<bool> vis;
    vector<int> used;

    vis.resize(n + 1);

    used.resize(n + 1);

    dist[1] = 0;
    q.push(1);

    bool finish = false;

    while (!q.empty()) {
        if (finish)
            break;

        int x = q.front();
        q.pop();
        vis[x] = false;

        for (auto i : adjList[x])
            if (dist[i.first] > dist[x] + i.second) {
                ++used[i.first];

                if (used[i.first]  == n) {
                    fout << "Ciclu negativ!";
                    finish = true;
                    break;
                }

                dist[i.first] = dist[x] + i.second;

                if (vis[i.first] == false) {
                    q.push(i.first);
                    vis[i.first] = true;
                }
            }
    }

    if (!finish)
        for (int i = 2; i <= n; i++)
            fout << dist[i] << " ";
}

void Graph :: royFloyd() {
    ifstream fin("royfloyd.in");
    ofstream fout("royfloyd.out");

    int n;

    fin >> n;

    adjList.resize(n + 1, vector<int> (n + 1, 0));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            fin >> adjList[i][j];
            if (adjList[i][j] == 0 && i != j)
                adjList[i][j] = INF;
        }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                if (adjList[j][i] + adjList[i][k] < adjList[j][k])
                    adjList[j][k] = adjList[j][i] + adjList[i][k];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            fout << adjList[i][j] << " ";
        fout << '\n';
    }
}

void Graph :: readDarb() {
    ifstream fin("darb.in");

    fin >> n;

    this -> n = n;
    adjList.resize(n + 1, vector<int> (n + 1, 0));

    for (int i = 0; i < n - 1; i++) {
        int a, b;
        fin >> a >> b;
        adjList[a].push_back(b);
        adjList[b].push_back(a);
    }
}

void Graph :: bfsDarb(int node) {
    vector<int> dist(n);
    queue<int> q;

    q.push(node);
    dist[node] = 1;
    int maxim = node;

    while (!q.empty()) {
        int x = q.front();
        last = x;
        for (auto y : adjList[x]) {
            if (!dist[y]) {
                dist[y] = dist[x] + 1;
                q.push(y);
            }
        }
        q.pop();
    }

    diam = dist[last];
}

void Graph :: solDarb() {
    ofstream fout("darb.out");
    bfsDarb(1);
    bfsDarb(last);
    fout << diam;
}
int main()
{
    /* dfs O(n + m)
    UndirectedGraph X = UndirectedGraph("dfs.in");
    X.dfsCompConex("dfs.out");
    */

    /* bfs O(n + m)
    DirectedGraph X = DirectedGraph("bfs.in");
    X.bfs(2);
    X.getBfs("bfs.out");
    */
    /* Top Sort O(n + m)
    DirectedGraph X = DirectedGraph("sortaret.in");
    X.topSort("sortaret.out");
    */
    UndirectedWeightedGraph X = UndirectedWeightedGraph("apm.in");
    X.apm("apm.out");
    return 0;
}