#include <fstream>
#include <vector>
#include <climits>
#define w 3000
using namespace std;
int n,m;
struct nod{int v,c;};
int d[w];bool viz[w];
vector <nod> a[w];
void dij()
{
    int ii,min,poz,i;
    nod t;
    for (ii=1;ii<=n;ii++)
    {
        min=INT_MAX;
        for (i=1;i<=n;i++)
        {
            if ((!viz[i])&&d[i]<min) min=d[i],poz=i;
        }
        viz[poz]=1;
        for (i=0;i<=a[poz].size()-1;i++)
        {
            t=a[poz][i];
            if (d[poz]+t.c<d[t.v]) d[t.v]=d[poz]+t.c;
        }
    }
}
int main()
{
    ifstream f("dijk.in");
    ofstream g("dijk.out");
    int t,i,ii,aux,x,s;
    nod y;
    f>>t;
    for (ii=1;ii<=t;ii++)
    {
        f>>n>>m;
        for (i=1;i<=m;i++)
        {
            f>>x>>y.v>>y.c;
            a[x].push_back(y);
            aux=y.v;y.v=x;x=aux;
            a[x].push_back(y);
        }
        f>>s;
        for (i=1;i<=n;i++) d[i]=INT_MAX,viz[i]=0;
        d[s]=0;
        dij();
        for (i=1;i<=n;i++)
        {
            a[i].erase(a[i].begin(),a[i].begin()+a[i].size()-1);
        }
        for (i=1;i<=n;i++)
        {
            if (i!=s)
            {
                if (d[i]!=INT_MAX) g<<d[i]<<' ';
                else g<<"-1 ";
            }
        }
        g<<'\n';
    }
    f.close();
    g.close();
    return 0;
}