#include <iostream>

using namespace std;
int main()
{
    int v;
    cin >> v;
    int e;
    cin >> e;
    int **tablica = new int*[v];
    for(int i=0;i<v;i++)
    {
        *(tablica+i) = new int[v];
    }
    for(int i=0;i<v;i++)
    {
        for(int t=0;t<v;t++)
        {
            if(t == i)
                tablica[i][t] = 0;
            else
            {
                tablica[i][t] = -1;
            }
        }
    }
    int p,k,w;
    for(int i=0;i<e;i++)
    {
        cin >> p >> k >> w;
        p -= 1; k -= 1;
        cout << p << k;
        tablica[p][k] = w;
        cout << tablica[p][k] << endl;
    }

    int x;
    cin >> x;
    x -= 1;
    cout << x << endl;
    int * pierwszy = new int[v];
    for(int i=0;i<v;i++)
    {
        pierwszy[i] = tablica[x][i];
    }
    for(int i=0;i<v;i++)
    {
        for(int t=0;t<v;t++)
        {
            if(pierwszy[t] == -1)
            {
                if(tablica[i][t] != -1 && pierwszy[i] != -1)
                    pierwszy[t] = tablica[i][t] + pierwszy[i];
            }
            else
            {
                if(tablica[i][t]+pierwszy[i] < pierwszy[t] && tablica[i][t] != -1 && pierwszy[i] != -1)
                    pierwszy[t] = tablica[i][t] + pierwszy[i];
            }
        }
    }
    for(int i=0;i<v;i++)
    {
        if(pierwszy[i] != -1)
            cout << "Od " << x+1 << " do " << i+1 << " wynosi: " << pierwszy[i] << " " << endl;
        else
            cout << "Od " << x+1 << " do " << i+1 << " wynosi: " << "nie ma" << " " << endl;
    }
    int sd;
    cin >> sd;
    return 0;
}