static class Graph {
private class Vertex {// class with a hashmap to hold the neighbours of a vertex and the edge cost
HashMap<String, Integer> nbrs = new HashMap<>();
}
HashMap<String, Vertex> vtces;// hashmap to store the graph
public Graph() {
vtces = new HashMap<>();
}
public void addVertex(String vname) {
Vertex vtx = new Vertex();
this.vtces.put(vname, vtx);// empty vertex hashmap
}
public void addEdge(String vname1, String vname2, int cost) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if (vtx1 == null || vtx2 == null || vtx1.nbrs.containsKey(vname2)) {
return;
}
vtx1.nbrs.put(vname2, cost);
vtx2.nbrs.put(vname1, cost);
}
private class DjikstraPair implements Comparable<DjikstraPair> {
String vname;
String psf;
int cost;
@Override
public int compareTo(DjikstraPair o) {
return o.cost - this.cost;
}
}
public HashMap<String, Integer> djikstra(String src) {
HashMap<String, Integer> ans = new HashMap<>();
HashMap<String, DjikstraPair> map = new HashMap<>();
HeapGeneric<DjikstraPair> heap = new HeapGeneric<>();
// make a pair and put in heap and map
for (String key : vtces.keySet()) {
DjikstraPair np = new DjikstraPair();
np.vname = key;
np.psf = "";
np.cost = Integer.MAX_VALUE;
if (key == src) {
np.cost = 0;
np.psf = key;
}
heap.add(np);
map.put(key, np);
}
// till the heap is not empty keep on removing the pair
while (!heap.isEmpty()) {
// remove a pair
DjikstraPair rp = heap.remove();
map.remove(rp.vname);
// add to ans
ans.put(rp.vname, rp.cost);
// nbrs
for (String nbr : vtces.get(rp.vname).nbrs.keySet()) {
// work for nbrs which are in heap
if (map.containsKey(nbr)) {
// get oc and nc
int oc = map.get(nbr).cost;
int nc = rp.cost + vtces.get(rp.vname).nbrs.get(nbr);
// update the pair only when nc<oc
if (nc < oc) {
DjikstraPair gp = map.get(nbr);
gp.psf = rp.psf + nbr;
gp.cost = nc;
heap.updatePriority(gp);
}
}
}
}
return ans;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t--!=0) {
int n = sc.nextInt();
int m = sc.nextInt();
Graph g = new Graph();
for(int i=1;i<=n;i++) {
g.addVertex(""+i);
}
for(int i=0;i<m;i++) {
g.addEdge(""+sc.nextInt(), ""+sc.nextInt(), sc.nextInt());
}
int s = sc.nextInt();
System.out.println(g.djikstra(""+s));
}
}