import java.util.*;
public class Main {
public class Heap_Genric<T extends Comparable> {
private ArrayList<T> data = new ArrayList<T>();
private HashMap<T, Integer> map = new HashMap<>();
public void add(T item) {
this.data.add(item);
map.put(item, this.data.size() - 1);
upheapify(this.data.size() - 1);
}
private void upheapify(int ci) {
// TODO Auto-generated method stub
int pi = (ci - 1) / 2;
if (isLarger(this.data.get(ci), this.data.get(pi)) > 0) {
swap(pi, ci);
upheapify(pi);
}
}
private void swap(int pi, int ci) {
// TODO Auto-generated method stub
T ith = this.data.get(pi);
T jth = this.data.get(ci);
this.data.set(pi, jth);
this.data.set(ci, ith);
map.put(ith, ci);
map.put(jth, pi);
}
public T remove() {
T rv;
swap(0, this.data.size() - 1);
rv = this.data.remove(this.data.size() - 1);
map.remove(rv);
downheapify(0);
return rv;
}
public boolean isEmpty() {
return this.data.isEmpty();
}
public int size() {
return this.data.size();
}
private void downheapify(int pi) {
// TODO Auto-generated method stub
int lci = (2 * pi + 1);
int rci = (2 * pi + 2);
int mini = pi;
if (lci < this.data.size() && isLarger(this.data.get(lci), this.data.get(mini)) > 0) {
mini = lci;
}
if (rci < this.data.size() && isLarger(this.data.get(rci), this.data.get(mini)) > 0) {
mini = rci;
}
if (mini != pi) {
swap(mini, pi);
downheapify(mini);
}
}
public int isLarger(T t, T o) {
return t.compareTo(o);
}
public void update_Priority(T pair) {
int index = map.get(pair);
upheapify(index);
}
}
public class Vertex {
HashMap<Integer, Integer> nbrs = new HashMap<>();
}
HashMap<Integer, Vertex> vtces = new HashMap<>();
public void addVertex(int vname) {
Vertex vtx = new Vertex();
vtces.put(vname, vtx);
}
public void addEdge(int vname1, int vname2, int cost) {
Vertex vtx1 = this.vtces.get(vname1);
Vertex vtx2 = this.vtces.get(vname2);
if (vtx1 == null || vtx2 == null || vtx1.nbrs.containsKey(vname2)) {
return;
}
vtx1.nbrs.put(vname2, cost);
vtx2.nbrs.put(vname1, cost);
}
public class DijkPair implements Comparable<DijkPair> {
int vname;
String aqvname;
int cost;
@Override
public int compareTo(DijkPair o) {
// TODO Auto-generated method stub
return o.cost - this.cost;
}
}
public void display() {
ArrayList<Integer> keys = new ArrayList<Integer>(this.vtces.keySet());
for (int key : keys) {
Vertex vtx = this.vtces.get(key);
System.out.println(key + " ->" + vtx.nbrs);
}
System.out.println("-------------");
}
public void Dijk(int src) {
HashMap<Integer, Integer> ans = new HashMap<>();
HashMap<Integer, DijkPair> map = new HashMap<>();
Heap_Genric<DijkPair> heap = new Heap_Genric<DijkPair>();
for (int key : this.vtces.keySet()) {
DijkPair np = new DijkPair();
np.vname = key;
if (key == src) {
np.aqvname = key + "";
np.cost = 0;
map.put(key, np);
heap.add(np);
continue;
}
np.aqvname = null;
np.cost = Integer.MAX_VALUE;
map.put(key, np);
heap.add(np);
}
while (!heap.isEmpty()) {
DijkPair rp = heap.remove();
map.remove(rp.vname);
ans.put(rp.vname, rp.cost);
for (int nbr : this.vtces.get(rp.vname).nbrs.keySet()) {
if (map.containsKey(nbr)) {
DijkPair gp = map.get(nbr);
int oc = gp.cost;
int nc = rp.cost + this.vtces.get(rp.vname).nbrs.get(nbr);
if (nc < oc) {
gp.cost = nc;
gp.aqvname = "" + rp.aqvname + gp.vname;
heap.update_Priority(gp);
}
}
}
}
ans.remove(src);
ArrayList<Integer> lis = new ArrayList<>(ans.keySet());
Collections.sort(lis);
for (int val : lis) {
if (ans.get(val) == Integer.MAX_VALUE) {
System.out.print(-1 + " ");
}
System.out.print(ans.get(val) + " ");
}
}
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int t = scn.nextInt();
while (t > 0) {
Main mm = new Main();
int n, m;
n = scn.nextInt();
m = scn.nextInt();
while (m > 0) {
int x, y, r;
x = scn.nextInt();
y = scn.nextInt();
r = scn.nextInt();
if (!mm.vtces.containsKey(x)) {
mm.addVertex(x);
}
if (!mm.vtces.containsKey(y)) {
mm.addVertex(y);
}
mm.addEdge(x, y, r);
// calling of Dijkstra Algorithm
m--;
}
int s = scn.nextInt();
mm.display();
mm.Dijk(s);
System.out.println();
t--;
}
}
}