import java.util.*;
public class Main {
HashMap<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
public Main(int n) {
// TODO Auto-generated constructor stub
for (int i = 1; i <= n; i++) {
map.put(i, new HashMap<>());
}
}
public void addedge(int v1, int v2, int cost) {
map.get(v1).put(v2, cost);
map.get(v2).put(v1, cost);
}
public void display() {
System.out.println(map);
}
public class DijikstraPair {
int vtx;
String path;
int cost;
public DijikstraPair(int vtx, String path, int cost) {
this.vtx = vtx;
this.path = path;
this.cost = cost;
}
@Override
public String toString() {
return this.cost + " ";
}
}
public void DijikstraAlgo(int src) {
PriorityQueue<DijikstraPair> q = new PriorityQueue<>(new Comparator<DijikstraPair>() {
@Override
public int compare(DijikstraPair o1, DijikstraPair o2) {
// TODO Auto-generated method stub
return o1.cost - o2.cost;// MinHeap and sorting on basis of rank but in MinHeap o1-o2
}
});
HashSet<Integer> visited = new HashSet<>();
int count = 0;
q.add(new DijikstraPair(src, "" + src, 0));
while (!q.isEmpty()) {
DijikstraPair rp = q.poll();
if (visited.contains(rp.vtx)) {
continue;
}
visited.add(rp.vtx);
if(rp.cost!=0) {
System.out.print(rp);
count++;
}
for (int nbrs : map.get(rp.vtx).keySet()) {
if (!visited.contains(nbrs)) {
q.add(new DijikstraPair(nbrs, rp.path + nbrs, rp.cost + map.get(rp.vtx).get(nbrs)));
}
}
}
while (count < map.size()-1) {
System.out.print("-1 ");
count++;
}
System.out.println();
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
Main bf = new Main(n);
int m = sc.nextInt();
for (int i = 1; i <= m; i++) {
int v1 = sc.nextInt();
int v2 = sc.nextInt();
bf.addedge(v1, v2, 6);
}
int src = sc.nextInt();
// bf.display();
bf.DijikstraAlgo(src);
// for (int j = 1; j <= n; j++) {
// if (j != src) {
// System.out.println(j);
// System.out.print(bf.BFS(src, j, 0) + " ");
// }
// }
// System.out.println();
// }
}
}
}