import java.util.*;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
private class Vertex{
HashMap<Integer,Integer> nbrs = new HashMap<>();
}
HashMap<Integer,Vertex> vtces;
public Main() {
this.vtces = new HashMap<>();
}
//********************Generic Heap*********************
private class GenericHeap<T extends Comparable<T>> {
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(ci,pi);
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,this.data.size()-1);
T rv = this.data.remove(this.data.size()-1);
map.remove(rv);
downheapify(0);
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(mini,pi);
downheapify(mini);
}
}
public T get() {
return this.data.get(0);
}
//If t is having higher priority then return positive value else return negative value
public int isLarger(T t,T o) {
return t.compareTo(o);
}
public void updatePriority(T pair) {
int index = map.get(pair);
upheapify(index);
}
}
public int numVertex() {
return this.vtces.size();
}
public boolean containsVertex(int vname) {
return this.vtces.containsKey(vname);
}
public void addVertex(int vname) {
Vertex vtx = new Vertex();
vtces.put(vname, vtx);
}
public void removeVertex(String vname) {
Vertex vtx = vtces.get(vname);
ArrayList<Integer> keys = new ArrayList<>(vtx.nbrs.keySet());
for(Integer key:keys) {
Vertex nbrvtx = vtces.get(key);
nbrvtx.nbrs.remove(vname);
}
vtces.remove(vname);
}
public int numEdges() {
ArrayList<Integer> keys = new ArrayList<>(vtces.keySet());
int count=0;
for(Integer key:keys) {
Vertex vtx = vtces.get(key);
count = count + vtx.nbrs.size();
}
return count/2;
}
public boolean containsEdge(int vname1,int vname2) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null || vtx2==null || !vtx1.nbrs.containsKey(vname2)) {
return false;
}
return true;
}
public void addEdge(int vname1,int 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);
}
public void removeEdge(int vname1,int vname2) {
Vertex vtx1 = vtces.get(vname1);
Vertex vtx2 = vtces.get(vname2);
if(vtx1==null || vtx2==null || !vtx1.nbrs.containsKey(vname2)) {
return;
}
vtx1.nbrs.remove(vname2);
vtx2.nbrs.remove(vname1);
}
public void display() {
System.out.println("------------------------------------------");
ArrayList<Integer> keys = new ArrayList<>(vtces.keySet());
for(Integer key:keys) {
Vertex vtx = vtces.get(key);
System.out.println(key+" : "+vtx.nbrs);
}
System.out.println("-------------------------------------------");
}
private class DjikstraPair implements Comparable<DjikstraPair>{
int vname;
int psf;
int cost;
public int compareTo(DjikstraPair o){
return o.cost-this.cost;
}
}
public HashMap<Integer,Integer> djikstra(int src) {
HashMap<Integer,DjikstraPair> map = new HashMap<>();
HashMap<Integer,Integer> ans = new HashMap<>();
GenericHeap<DjikstraPair> heap = new GenericHeap<>();
//make a pair
for(Integer key:vtces.keySet()) {
DjikstraPair np = new DjikstraPair();
np.vname = key;
np.psf = 0;
np.cost = Integer.MAX_VALUE;
if(key == src) {
np.cost = 0;
np.psf = key;
}
heap.add(np);
map.put(key, np);
}
while(!heap.isEmpty()) {
//remove a pair
DjikstraPair rp = heap.remove();
map.remove(rp.vname);
//add to ans
if(rp.cost>0) {
ans.put(rp.vname, rp.cost);
}
//nbrs
for(Integer nbr:vtces.get(rp.vname).nbrs.keySet()) {
//work for nbrs in heap
if(map.containsKey(nbr)) {
int oldcost = map.get(nbr).cost;
int newcost = rp.cost + vtces.get(rp.vname).nbrs.get(nbr);
//update only when newcost is less than oldcost
if(newcost < oldcost) {
DjikstraPair gp = map.get(nbr);
gp.psf = rp.psf + nbr;
gp.cost = newcost;
heap.updatePriority(gp);
}
}
}
}
return ans;
}
public static void main(String[] args) {
Main g = new Main();
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while(T-->0) {
int N = sc.nextInt();
int M = sc.nextInt();
for(int i=0;i<N;i++) {
int x =sc.nextInt();
int y = sc.nextInt();
int r = sc.nextInt();
if(!g.containsVertex(x)) {
g.addVertex(x);
}
if(!g.containsVertex(y)) {
g.addVertex(y);
}
g.addEdge(x, y, r);
}
int src = sc.nextInt();
HashMap<Integer,Integer> m = g.djikstra(src);
ArrayList<Integer> list = new ArrayList<>(m.keySet()) ;
for(Integer key:list) {
System.out.print(m.get(key)+" ");
}
}
}
}
//sir Iām getting correct and for the given case but Iām not getting how to tackle the case for -1 cost and this implementation is also quite long to implement. Can you suggest any changes