题目描述
暗黑法王JZL的爪牙几乎渗透了整个魔法世界，你所在的学院“兰亭园”成为唯一安全的地方，为了对抗邪恶的暗黑法王，学院的法师们需要不停地修炼自己的法术，而当他们修炼到一定程度时，就可以进阶成下一阶魔法师。比如最开始所有学员都是白袍魔法师，可以进阶成蓝袍法师，黄袍法师、绿袍法师……然而大部分法师在暗黑法王面前都是弟弟，只有红袍法师才能与之抗衡，可惜学院迄今为止没有一个法师能够修炼成红袍法师，时间紧迫，还好学院有祖先们传下来的水晶，这些水晶蕴含着强大的能量，可以让一个法师直接进阶到下一阶法师，非常好用。现在已知学院已有的法师种类和进阶关系，要用最少的水晶产生一个红袍法师，水晶数量有限，魔法协会会长GHX将这个任务交给了优秀的你，你能为他解决这个问题吗？
输入
首先第一行输入四个整数N（1 <= N <= 1000），M （1 <= M <= 100000），K（1 <= N - 1），S（1 <= S <= N）, 分别表示有N种法师，M种进阶关系，初始拥有的法师种类数量，和红袍法师的编号，第二行输入K个整数ai（1 <= ai <= N），表示K个初始法师的编号，第3行到第M + 2行每行输入三个整数U，V(1 <= U, V <= N)，W（1 <= W <= 100000），表示U法师可以花费W个水晶进阶为V法师。某法师进阶到另一法师的途径不一定唯一，也可能存在进阶到原来的法师等级的情况。
输出
一个整数表示产生红袍法师所需要的最少水晶数量，如果无法产生，输出“GG“。（不带引号）
8 10 3 8
3 4 5
2 1 2
1 3 1
3 2 6
3 5 8
3 4 2
4 7 3
5 7 5
4 6 4
6 8 2
7 8 4