#include <fstream>
#include <stdlib.h>
#define inf 1000000000
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
int n,i,m,C[100][100],d[100],pre[100],s,o[100];
void init()
{
    int i,x,y,j,c;
    fin>>n>>m>>s;
    o[s]=1;
    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++)
            {C[i][j]=inf; C[j][i]=inf;}
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        C[x][y]=c;
    }
    for (i=1;i<=n;i++)
    {
        d[i]=C[s][i];
        pre[i]=s;
    }
    pre[s]=0;
}
void Dijkstra()
{
    int i,M,v,j;
    for (j=1;j<n;j++)
    {
        M=inf;
        for (i=1;i<=n;i++)
            if (!o[i]&&d[i]<M)
            {
                M=d[i];
                v=i;
            }
        o[v]=1;
        for (i=1;i<=n;i++)
            if (!o[i]&&d[i]>d[v]+C[v][i])
        {
            d[i]=d[v]+C[v][i];
            pre[i]=v;
        }
    }
}
void afisare()
{
    int i,drum[100],lg,v,j;
    for (i=1;i<=n;i++)
    {
        fout<<"nodul "<<i<<": lungimea:"<<d[i]<<" drum: ";
        if (d[i])
        {
            v=i; lg=0;
            while (pre[v])
            {
                lg++;
                drum[lg]=v;
                v=pre[v];
            }
            for (j=lg;j>=1;j--) fout<<drum[j]<<" ";
        }
        fout<<'\n';
    }
}
int main()
{
    init();
    Dijkstra();
    afisare();
    fin.close();
    fout.close();
    return 0;
}