static class HeapGeneric<T extends Comparable> {
ArrayList<T> data = new ArrayList<>();
HashMap<T, Integer> map = new HashMap<>();
public void add(T item) {
data.add(item);
map.put(item, data.size() - 1);
upheapify(data.size() - 1);
}
private void upheapify(int ci) {
int pi = (ci - 1) / 2;
if (isLarger(data.get(ci), data.get(pi)) > 0) {
swap(pi, ci);
upheapify(pi);
}
}
private void swap(int i, int j) {
T ith = data.get(i);
T jth = data.get(j);
data.set(i, jth);
data.set(j, ith);
map.put(ith, j);
map.put(jth, i);
}
public void display() {
System.out.println(data);
}
public int size() {
return this.data.size();
}
public boolean isEmpty() {
return this.size() == 0;
}
public T remove() {
swap(0, data.size() - 1);
T rv = this.data.remove(this.data.size() - 1);
downHeapify(0);
map.remove(rv);
return rv;
}
private void downHeapify(int pi) {
int lci = 2 * pi + 1;
int rci = 2 * pi + 2;
int mini = pi;
if (lci < this.data.size() && isLarger(data.get(lci), data.get(mini)) > 0) {
mini = lci;
}
if (rci < this.data.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);
}
// if t is having higher priority then return +ve value
public int isLarger(T t, T o) {
return t.compareTo(o);
}
public void updatePriority(T pair) {
int index = map.get(pair);
upheapify(index);
}
}
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.equals(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();
HashMap<String, Integer> ans = g.djikstra("" + s);
for (String key : ans.keySet()) {
if (!key.equals("" + s)) {
System.out.print(ans.get(key) + " ");
}
}
System.out.println();
}
}