#include <iostream>
#include <fstream>
#define nmax 101
#define inf 10001

using namespace std;


int c[nmax][nmax],uz[nmax],d[nmax],o[nmax];
int x0;
int n,m;

ifstream fin("in.in");
ofstream fout("out.out");

void initializare()
{
    int i,j,x,y;
    fin>>n>>m;
    int q;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        c[i][j]= inf;
    for(i=1;i<=n;i++)
        c[i][i]=0;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>q;
        c[x][y]=q;
    }
    for(i=1;i<=n;i++)
    {
        d[i]=c[x0][i];
        o[i]=x0;
    }
    o[x0]=0;
    uz[x0]=1;
}

void afisare()
{
    int i,j, ord[nmax], pos;
    {
        for(i=1;i<=n;i++)
           if(i!=x0)
           {
               fout<<"cost "<<d[i];
               fout<<" drumul ";
               pos = 0;
               ord[0]=i;
               while(o[ord[pos]])
               {
                   pos++;
                   ord[pos]=o[ord[pos-1]];
               }
               for(j=pos;j>=0;j--)
                fout<<ord[j]<<" ";
               fout<<"\n";
           }
    }
}



int main()
{
    fin>>x0;
    int i,j,co,vfcrt;
    initializare();
    for(j=1;j<n;j++)
    {
        co = inf;
        for(i=1;i<=n;i++)
        if(!uz[i] && co > d[i])
        {
            co = d[i];
            vfcrt = i;
        }

        uz[vfcrt]= 1;

        for(i=1;i<=n;i++)
        if(!uz[i] && d[i] > co + c[vfcrt][i])
        {
            o[i]=vfcrt;
            d[i]=co + c[vfcrt][i];
        }
    }
    afisare();
}