import java.util.*;
public class Main {
public class Vertex{
String name;
HashMap<Vertex, Integer> nbrs;
Vertex(String name){
this.name=name;
nbrs= new HashMap<Vertex, Integer>();
}
public void display() {
String str=this.name;
str=str+"=>";
Set<Vertex> nbrs = this.nbrs.keySet();
for(Vertex nbr : nbrs) {
str = str + nbr.name + "(" + this.nbrs.get(nbr) + "),";
}
str=str + "END";
System.out.println(str);
}
}
HashMap<String, Vertex> vtces;
Main(){
this.vtces= new HashMap<String,Vertex>();
}
public void addVertex(String name) {
if(this.vtces.containsKey(name)) {
return;
}
Vertex vtx = new Vertex(name);
this.vtces.put(name,vtx);
}
public void addEdge(String name1, String name2, int cost) {
if(!this.vtces.containsKey(name1)||!this.vtces.containsKey(name2))
return;
Vertex vtx1 = this.vtces.get(name1);
Vertex vtx2 = this.vtces.get(name2);
if(vtx1.nbrs.containsKey(vtx2))
return;
vtx1.nbrs.put(vtx2,cost);
vtx2.nbrs.put(vtx1,cost);
}
public int totalVtxs() {
return this.vtces.size();
}
public int totalEges() {
int ans=0;
Collection<Vertex> vtces = this.vtces.values();
for(Vertex vtx: vtces) {
ans = ans + vtx.nbrs.size();
}
ans = ans/2;
return ans;
}
public void removeVtx(String name) {
if(!this.vtces.containsKey(name))
return;
Vertex vtx = this.vtces.get(name);
Set<Vertex> nbrs = vtx.nbrs.keySet();
for(Vertex nbr:nbrs) {
nbr.nbrs.remove(vtx);
}
this.vtces.remove(name);
}
public void removeEdge(String name1, String name2) {
if(!this.vtces.containsKey(name1)||!this.vtces.containsKey(name2))
return;
Vertex vtx1 = this.vtces.get(name1);
Vertex vtx2 = this.vtces.get(name2);
if(!vtx1.nbrs.containsKey(vtx2))
return;
vtx1.nbrs.remove(vtx2);
vtx2.nbrs.remove(vtx1);
}
public void display() {
Collection<Vertex> vtces = this.vtces.values();
for(Vertex vtx : vtces) {
vtx.display();
}
}
public void dijkstrasAgo(String source) {
int [] dis = new int[this.vtces.size()];
for(int i=0;i<dis.length;i++) {
dis[i]=Integer.MAX_VALUE;
}
Queue<String> q = new LinkedList<>();
Vertex vtx = this.vtces.get(source);
dis[Integer.parseInt(source)-1]=0;
q.add(source);
HashMap<String ,Boolean> visited = new HashMap<>();
visited.put(source,true);
while(!q.isEmpty()) {
String rv = q.remove();
Vertex v = this.vtces.get(rv);
Set<Vertex> nbrs = v.nbrs.keySet();
for(Vertex nbr : nbrs) {
int oc = dis[Integer.parseInt(nbr.name)-1];
int nc = dis[Integer.parseInt(v.name)-1] + v.nbrs.get(nbr);
if(nc<oc) {
dis[Integer.parseInt(nbr.name)-1]=nc;
q.add(nbr.name);
if(!visited.containsKey(nbr.name))
visited.put(nbr.name,true);
}
}
}
Set<String> names = this.vtces.keySet();
for(String name : names) {
if(!visited.containsKey(name)) {
visited.put(name,true);
dis[Integer.parseInt(name)-1]=-1;
}
}
for(int i=1;i<dis.length;i++) {
System.out.print(dis[i] +" ");
}
}
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
Main graph = new Main();
int t = sc.nextInt();
for(;t>0;t--) {
int n = sc.nextInt();
for(int i=1;i<=n;i++) {
String str = Integer.toString(i);
graph.addVertex(str);
}
int m = sc.nextInt();
for(int i=1;i<=m;i++) {
String s = sc.next();
String e = sc.next();
int cost = sc.nextInt();
graph.addEdge(s, e, cost);
}
int s = sc.nextInt();
String source = Integer.toString(s);
graph.dijkstrasAgo(source);
}
}
}