#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9+7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, l;
    cin >> n >> m >> l;

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

    for(int i = 0; i < n; i++){
        if(i+1 == l) continue;
        sorrend.push_back(i+1);
    }
    for(int i = 1; i <= n; i++){
        legrovidebb[i][i] = 0;
    }

    int a, b, c;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        legrovidebb[a][b] = c;
        legrovidebb[b][a] = c;
    }

    // Floyd-Warshall
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(legrovidebb[i][k] < INF && legrovidebb[k][j] < INF){
                    legrovidebb[i][j] = min(legrovidebb[i][j], legrovidebb[i][k] + legrovidebb[k][j]);
                }
            }
        }
    }


    vector<int> jo_sorrend;
    int min_ossz = INF;

    do{
        int akt_ut = 0;
        int elozo = l;
        bool jo = true;
        for(int x : sorrend){
            akt_ut += legrovidebb[elozo][x];
            elozo = x;
        }
        akt_ut += legrovidebb[elozo][l];
        if(!jo) continue;

        if(akt_ut < min_ossz){
            min_ossz = akt_ut;
            jo_sorrend.clear();
            for(int x : sorrend){
                jo_sorrend.push_back(x);
            }
        }
    }while(next_permutation(sorrend.begin(), sorrend.end()));

    cout << min_ossz << "\n";
    for(int x : jo_sorrend){
        cout << x << " ";
    }
    cout << "\n";
}