/*
Author: Plamen Nachev
Algorithm of Ford-Bellman on oriented graph.
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 100;

struct Edge
{
    int from, to, price;
    Edge( int f, int t, int p ) : from(f), to(t), price(p) {}
};

vector <Edge> edges;

int N, M, start;

void input()
{
    scanf("%d %d", &N, &M);
    int first, second, price;
    for( int i = 0; i < M; i++ )
    {
        scanf("%d %d %d", &first, &second, &price);
        edges.push_back(Edge(first-1, second-1, price));
    }
    scanf("%d", &start);
    start--;
}

int dist[MAXN], pred[MAXN];

void print_path( int s, int e )
{
    if( pred[e] == -1 )
    {
        printf("%d ", e+1);
        return;
    }
    print_path(s, pred[e]);
    printf("%d ", e+1);
}

void ford_bellman()
{
    memset(dist, 63, sizeof(dist));
    memset(pred, -1, sizeof(pred));
    dist[start] = 0;

    for( int i = 1; i <= N-1; i++ )
    {
        for( int j = 0; j < M; j++ )
        {
            if( dist[edges[j].to] > dist[edges[j].from] + edges[j].price )
            {
                dist[edges[j].to] = dist[edges[j].from] + edges[j].price;
                pred[edges[j].to] = edges[j].from;
            }
        }
    }
    printf("Minimal distances from %d to all other vertices:\n", start+1);
    for( int i = 0; i < N; i++ )
        printf("%d ", dist[i]);
    printf("\n");

    int s = 0, e = N-1; /// example nodes to search path between
    print_path(s, e);
    printf("\n");
}

int main()
{
    input();
    ford_bellman();
    return 0;
}
/**

Example 1:
5 4
1 2 1
2 3 3
3 4 2
4 5 5
1

Example 2:
5 4
4 5 5
3 4 2
2 3 3
1 2 1
1

Example 3: contains negative cycle: (program crashes when you try to print minimal path
                                       passing through negative cycles; endless loop happens)
7 7
4 5 4
2 3 2
1 2 1
7 4 -6
3 7 -5
5 6 5
4 3 3
1

**/