#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int nmax = 10000;
const int INF = 200000200;

int n, m, s;
vector<pair<pair<int, int>, int>> g;

ifstream fin("apm.in");
ofstream gout("apm.out");

void Prim(int s) {
    vector<int> d(n, INF);
    vector<int> tata(n, 0);
    vector<bool> q(n + 1, true);

    d[s] = 0;

    while (true) {
        int u = -1;
        for (int i = 1; i <= n; ++i) {
            if (q[i] && (u == -1 || d[i] < d[u])) {
                u = i;
            }
        }

        if (d[u] == INF) {
            break; // All nodes have been visited
        }

        q[u] = false; // Mark u as visited

        for (auto edge : g) {
            int v;
            if (edge.first.first == u) {
                v = edge.first.second;
            } else if (edge.first.second == u) {
                v = edge.first.first;
            } else {
                continue; // Skip edges not connected to the current node
            }

            int w = edge.second;

            if (q[v] && d[v] > w) {
                d[v] = w;
                tata[v] = u;
            }
        }

    }

    int totalCost = 0;
    for (int i = 1; i <= n; ++i) {
        if (i != s) {
            totalCost += d[i];
            gout << tata[i] << " " << i << "\n";
        }
    }

    gout << totalCost << "\n";
}

int main() {
    fin >> n >> m;
    while (m--) {
        int x, y, cost;
        fin >> x >> y >> cost;
        g.push_back({{x, y}, cost});
    }

    fin >> s;

    Prim(s);

    fin.close();
    gout.close();

    return 0;
}