#include <iostream>
#include <fstream>

#define Inf 10000

using namespace std;

void init();
void afisare();

int C[500][500];
int drumMin[500], varfMin[500];
int n, start;

bool M[500];

int main()
{
    int vMin, dMin;
    init();

    for(int i = 1; i < n; i++)
    {
        dMin = Inf;

        for(int j = 1; j <= n; j++)
        {
            if(!M[j] && drumMin[j] < dMin)
            {
                dMin = drumMin[j];
                vMin = j;
            }
        }

        M[vMin] = true;

        for(int j = 1; j <= n; j++)
        {
            if(!M[j] && drumMin[j] > dMin + C[vMin][j])
            {
                drumMin[j] = dMin + C[vMin][j];
                varfMin[j] = vMin;
            }
        }
    }

    afisare();

    return 0;
}

void init()
{
    ifstream in("in.txt");
    int x, y, c;

    in >> n >> start;

    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            C[i][j] = C[j][i] = Inf;
        }
    }

    while(in >> x >> y >> c)
    {
        C[x][y] = c;
    }

    for(int i = 1; i <= n; i++)
    {
        drumMin[i] = C[start][i];
    }

    for(int i = 1; i <= n; i++)
    {
        varfMin[i] = start;
    }

    varfMin[start] = 0;
    M[start] = true;
}

void afisare()
{
    int drum[500];
    int lg;

    for(int i = 1; i <= n; i++)
    {
        if(i != start)
        {
            drum[0] = varfMin[i];
            lg = 0;

            cout << start << " -> " << i << " - " << drumMin[i] << endl;

            while(varfMin[lg])
            {
                lg++;
                drum[lg] = varfMin[drum[lg - 1]];
            }

            for(int j = lg; j >= 0; j--)
            {
                cout << drum[j] << " ";
            }
            cout << endl;
        }
    }
}