#include<fstream>
#define INF 1000000000
using namespace std;
ifstream f("disktra.in");
ofstream g("disktra.out");
int n,m,i,j,t,mini,c,k,x,s,nr,y,heap[100],a[100][100],ord[100];
void creare(int i)
{
    int c=i,p=i/2;
    while(p)
    {
        if(heap[p]>heap[c])
        swap(heap[p],heap[c]),swap(ord[p],ord[c]);
        else
        break;
        c=p;
        p=p/2;
    }
}
void refa()
{
    int c,p;
    --nr;
    //swap(heap[1],heap[nr]);
    //swap(ord[1],ord[nr]);

    p=1;
    c=2;
    while(c<=nr)
    {
        if(c+1<=nr&&heap[c]>heap[c+1])
        c=c+1;
        if(heap[c]<heap[p])
        swap(heap[c],heap[p]),swap(ord[p],ord[c]);
        else
        break;
        p=c;
        c=2*c;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;++i)
    for(j=1;j<=n;++j)
    if(i!=j)
    a[i][j]=INF;
    for(i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    f>>s;
    for(i=1;i<=n;++i)
    {
        ++nr;
        heap[nr]=a[s][i];
        ord[nr]=i;
        creare(nr);
    }
    swap(heap[1],heap[nr]);
    swap(ord[1],ord[nr]);
    refa();

 //   viz[s]=1;
    for(t=n-1;t;--t)
    {
        mini=heap[1];
        if(mini==INF)
        break;
        k=ord[1];
//        refa(t);
        swap(heap[1],heap[nr]);
        swap(ord[1],ord[nr]);
        for(i=1;i<=nr;++i)
        if(heap[i]>mini+a[k][ord[i]])
        heap[i]=mini+a[k][ord[i]];
        refa();
    }
    for(i=1;i<=n;++i)
    g<<heap[i]<<' '<<ord[i]<<'\n';
    return 0;
}