import java.util.*;
public class Main {
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int f=0;f<t;f++){
Graph g=new Graph();
int n=sc.nextInt();
int m=sc.nextInt();
for(int i=1;i<=n;i++){
g.addVertex(i+"");
}
for(int i=0;i<m;i++){
int x=sc.nextInt();
int y=sc.nextInt();
int r=sc.nextInt();
g.addEdge(x+"",y+"",r);
}
g.Dijkstra(sc.nextInt()+"");
}
}
}
class HeapGeneric<T extends Comparable> {
ArrayList data=new ArrayList();
HashMap<T,Integer> Index=new HashMap<>();
// Add an Element.
public void add(T item){
data.add(item);
Index.put(item,this.data.size()-1);
upheapify(data.size()-1);
}
public int size(){
return data.size();
}
public void upheapify(int ci){
int pi=(ci-1)/2;
if((isLarger(data.get(ci),data.get(pi)))>0){
swap(pi,ci);
upheapify(pi);
}
else
return;
}
public void swap(int i,int j){
T ith=data.get(i);
T jth=data.get(j);
data.set(i,jth);
data.set(j,ith);
Index.put(ith,j);
Index.put(jth,i);
}
public T remove(){
swap(0,size()-1);
T rv=data.remove(size()-1);
Index.remove(rv);
downheapify(0);
return rv;
}
public boolean isEmpty(){
return (this.data.size()==0);
}
public void downheapify(int pi){
int mini=pi;
int lci=pi*2+1;
int rci=pi*2+2;
if(lci<size() && isLarger(data.get(lci),data.get(mini))>0){
mini=lci;
}
if(rci<size() && isLarger(data.get(rci),data.get(mini))>0){
mini=rci;
}
if(mini!=pi){
swap(pi,mini);
downheapify(mini);
}
}
public T get(){
return this.data.get(0);
}
public int isLarger(T t,T o){
return t.compareTo(o);
}
public void updatePriority(T pair){
int ind=Index.get(pair);
upheapify(ind);
}
}
class Graph {
HashMap<String,Vertex> vtces=new HashMap<>();
private class Vertex{
String vname;
HashMap<String,Integer> nbrs;
Vertex(String vname){
this.vname=vname;
nbrs=new HashMap<String,Integer>();
}
}
// add an Vertex
public void addVertex(String vname){
Vertex vtx=new Vertex(vname);
this.vtces.put(vname,vtx);
}
//Return number of vertices.
public int numVertex(){
return this.vtces.size();
}
//Contains vertex
public boolean containsVertex(String vertex){
return this.vtces.containsKey(vertex);
}
// Add an Edge
public void addEdge(String vname1,String vname2,int cost){
Vertex vtx1=this.vtces.get(vname1);
Vertex vtx2=this.vtces.get(vname2);
if(vtx1!=null && vtx2!=null) {
if (vtx1.nbrs.containsKey(vname2) && vtx2.nbrs.containsKey(vname1)) {
if(vtx1.nbrs.get(vname2)>cost){
vtx1.nbrs.put(vname2,cost);
vtx2.nbrs.put(vname1,cost);
}
else
{
}
}
else{
vtx1.nbrs.put(vname2,cost);
vtx2.nbrs.put(vname1,cost);
}
}
}
// Return number of Edges
public int numEdges(){
Set<String> set=vtces.keySet();
int sum=0;
for(String str:set){
sum+=vtces.get(str).nbrs.size();
}
return sum/2;
}
// PRIVATE CLASS PAIRS
private class DijkstraPair implements Comparable<DijkstraPair>{
String vname;
String acqvname;
int cost;
DijkstraPair(String vname){
this.vname=vname;
acqvname=null;
cost=Integer.MAX_VALUE;
}
public int compareTo(DijkstraPair o){
return o.cost-this.cost;
}
}
public int getEdge(String str1,String str2){
if(str1.equals(str2) || !vtces.get(str1).nbrs.containsKey(str2))
return 0;
else
return vtces.get(str1).nbrs.get(str2);
}
public void Dijkstra(String src){
HashMap<String,Integer> ans=new HashMap<>();
Set<String> set=vtces.keySet();
HeapGeneric<DijkstraPair> heap=new HeapGeneric<>();
HashMap<String,DijkstraPair> track=new HashMap<>();
for(String key:set){
DijkstraPair dp=new DijkstraPair(key);
heap.add(dp);
track.put(key,dp);
}
track.get(src).cost=0;
heap.updatePriority(track.get(src));
HashMap<String,Integer> visited=new HashMap<>();
int prev=0;
while(!heap.isEmpty()){
DijkstraPair dp=heap.remove();
visited.put(dp.vname,1);
prev=dp.cost;
if(prev>=Integer.MAX_VALUE)
prev=-1;
ans.put(dp.vname,prev);
set=vtces.get(dp.vname).nbrs.keySet();
for(String str:set){
if(!visited.containsKey(str)){
int newdist=prev+getEdge(str,dp.vname);
int old=track.get(str).cost;
if(newdist<old){
track.get(str).cost=newdist;
heap.updatePriority(track.get(str));
//System.out.print(str+" : "+newdist+",");
}
}
}
// System.out.println();
}
set=ans.keySet();
//System.out.println(ans);
int a[]=new int[vtces.size()+1];
for(String str:set){
int b=Integer.parseInt(str);
a[b]=ans.get(str);
}
int j=Integer.parseInt(src);
for(int i=1;i<a.length;i++){
if(i!=j)
System.out.print(a[i]+" ");
}
System.out.println();
}
}