import java.util.*;
import java.io.*;
public class Main
{
static class node implements Comparable<node>
{
int goal;
int cost;
public node(int goal , int cost)
{
this.goal = goal;
this.cost = cost;
}
public int compareTo(node n)
{
return cost - n.cost;
}
}
static int n , m , x;
static ArrayList<node>[] list;
static PriorityQueue<node> pq; //매번하게 될 듯?
static boolean[] visit; //매번하게 될 듯?
static int[] value;
static boolean arrive; //목적지 도착 후 돌아갈 타이밍을 알기 위한 장치
{
n
= Integer.
parseInt(st.
nextToken()); m
= Integer.
parseInt(st.
nextToken()); x
= Integer.
parseInt(st.
nextToken());
value = new int[n+1];
for(int i = 1 ; i <= n ; i++)
{
list[i] = new ArrayList<>();
if(i
!= x
) value
[i
] = Integer.
MAX_VALUE; }
for(int i = 0 ; i < m ; i++)
{
int a
= Integer.
parseInt(st.
nextToken()); int b
= Integer.
parseInt(st.
nextToken()); int c
= Integer.
parseInt(st.
nextToken());
list[b].add(new node(a,c));
}
for(int i = 1 ; i <= n ; i++)
{
}
bfs(x);
int max = 0;
for(int i = 1 ; i <= n ; i++)
{
//System.out.println(value[i]);
max
= Math.
max(value
[i
],max
); }
}
public static void bfs(int start)
{
visit = new boolean[n+1];
arrive = false;
pq = new PriorityQueue<>();
pq.add(new node(start,0));
while(!pq.isEmpty())
{
node nod = pq.poll();
if(visit[nod.goal]) continue;
visit[nod.goal] = true;
for(int i = 0 ; i < list[nod.goal].size() ; i++)
{
node next = list[nod.goal].get(i);
if(!visit[next.goal] && value[next.goal] > value[nod.goal] + next.cost)
{
value[next.goal] = value[nod.goal] + next.cost;
pq.add(new node(next.goal , value[next.goal]));
}
}
}
}
}
aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5pby4qOwoKCnB1YmxpYyBjbGFzcyBNYWluCnsKCXN0YXRpYyBjbGFzcyBub2RlIGltcGxlbWVudHMgQ29tcGFyYWJsZTxub2RlPgoJewoJCWludCBnb2FsOwoJCWludCBjb3N0OwoJCQoJCXB1YmxpYyBub2RlKGludCBnb2FsICwgaW50IGNvc3QpCgkJewoJCQl0aGlzLmdvYWwgPSBnb2FsOwoJCQl0aGlzLmNvc3QgPSBjb3N0OwoJCX0KCQkKCQlwdWJsaWMgaW50IGNvbXBhcmVUbyhub2RlIG4pCgkJewoJCQlyZXR1cm4gY29zdCAtIG4uY29zdDsKCQl9Cgl9CglzdGF0aWMgaW50IG4gLCBtICwgeDsKCXN0YXRpYyBBcnJheUxpc3Q8bm9kZT5bXSBsaXN0OwoJc3RhdGljIFByaW9yaXR5UXVldWU8bm9kZT4gcHE7CS8v66ek67KI7ZWY6rKMIOuQoCDrk68/CglzdGF0aWMgYm9vbGVhbltdIHZpc2l0OwkvL+unpOuyiO2VmOqyjCDrkKAg65OvPwoJc3RhdGljIGludFtdIHZhbHVlOwoJc3RhdGljIGJvb2xlYW4gYXJyaXZlOwkvL+uqqeyggeyngCDrj4TssKkg7ZuEIOuPjOyVhOqwiCDtg4DsnbTrsI3snYQg7JWM6riwIOychO2VnCDsnqXsuZgKCQoJcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBJT0V4Y2VwdGlvbgoJewoJCUJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKCQlTdHJpbmdUb2tlbml6ZXIgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKGJyLnJlYWRMaW5lKCkpOwoJCQoJCW4gPSBJbnRlZ2VyLnBhcnNlSW50KHN0Lm5leHRUb2tlbigpKTsKCQltID0gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7CgkJeCA9IEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpOwoJCQoJCWxpc3QgPSBuZXcgQXJyYXlMaXN0W24rMV07CgkJdmFsdWUgPSBuZXcgaW50W24rMV07CiAgICAgICAgCgkJZm9yKGludCBpID0gMSA7IGkgPD0gbiA7IGkrKykKCQl7CgkJCWxpc3RbaV0gPSBuZXcgQXJyYXlMaXN0PD4oKTsKCQkJaWYoaSAhPSB4KSB2YWx1ZVtpXSA9IEludGVnZXIuTUFYX1ZBTFVFOwoJCX0KCQkKCQlmb3IoaW50IGkgPSAwIDsgaSA8IG0gOyBpKyspCgkJewoJCQlzdCA9IG5ldyBTdHJpbmdUb2tlbml6ZXIoYnIucmVhZExpbmUoKSk7CgkJCWludCBhID0gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7CgkJCWludCBiID0gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7CgkJCWludCBjID0gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7CgkJCQoJCQlsaXN0W2JdLmFkZChuZXcgbm9kZShhLGMpKTsKCQl9CgkJCgkJZm9yKGludCBpID0gMSA7IGkgPD0gbiA7IGkrKykKCQl7CgkJCUNvbGxlY3Rpb25zLnNvcnQobGlzdFtpXSk7CgkJfQoJCQoJCWJmcyh4KTsKCQkKCQlpbnQgbWF4ID0gMDsKCQlmb3IoaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrKQoJCXsKCQkJLy9TeXN0ZW0ub3V0LnByaW50bG4odmFsdWVbaV0pOwoJCQltYXggPSBNYXRoLm1heCh2YWx1ZVtpXSxtYXgpOwoJCX0KCQlTeXN0ZW0ub3V0LnByaW50bG4obWF4KTsKCX0KCXB1YmxpYyBzdGF0aWMgdm9pZCBiZnMoaW50IHN0YXJ0KQoJewoJCXZpc2l0ID0gbmV3IGJvb2xlYW5bbisxXTsKCQlhcnJpdmUgPSBmYWxzZTsKCQlwcSA9IG5ldyBQcmlvcml0eVF1ZXVlPD4oKTsKCQlwcS5hZGQobmV3IG5vZGUoc3RhcnQsMCkpOwoJCQoJCXdoaWxlKCFwcS5pc0VtcHR5KCkpCgkJewoJCQlub2RlIG5vZCA9IHBxLnBvbGwoKTsKCQkJCgkJCWlmKHZpc2l0W25vZC5nb2FsXSkgY29udGludWU7CgkJCXZpc2l0W25vZC5nb2FsXSA9IHRydWU7CgkJCQoJCQlmb3IoaW50IGkgPSAwIDsgaSA8IGxpc3Rbbm9kLmdvYWxdLnNpemUoKSA7IGkrKykKCQkJewoJCQkJbm9kZSBuZXh0ID0gbGlzdFtub2QuZ29hbF0uZ2V0KGkpOwoJCQkJCgkJCQlpZighdmlzaXRbbmV4dC5nb2FsXSAmJiB2YWx1ZVtuZXh0LmdvYWxdID4gdmFsdWVbbm9kLmdvYWxdICsgbmV4dC5jb3N0KQoJCQkJewoJCQkJCXZhbHVlW25leHQuZ29hbF0gPSB2YWx1ZVtub2QuZ29hbF0gKyBuZXh0LmNvc3Q7CgkJCQkJcHEuYWRkKG5ldyBub2RlKG5leHQuZ29hbCAsIHZhbHVlW25leHQuZ29hbF0pKTsKCQkJCX0KCQkJfQoJCX0KCX0KfQ==