观赛完运动会之后，花叶需要立马去BITTO的钢条厂上班，由于北航到钢条厂的路径有很多条，他希望选择一条最短的！
形式化来说，给一个 $n$ 个点 $m$ 条边的带权无向图，求点 $s$ 到点 $t$ 的最短路路径以及长度。
只能使用Python提交
第一行四个正整数 $n,m,s,t$，其中 $1 \leq n \leq 2.5 \times 10^3$，$1 \leq m\leq 7 \times 10^3$，$1 \le s,t \le n$，含义如题目所示。
第二行一个正整数 $p$，表示是否需要输出具体最短路径，$1$ 表示需要输出最短路径，$0$ 表示不需要。
接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$，其中$1 \le u_i, v_i \le n$，$1 \leq w_i \leq 10^3$，表示第 $i$ 条边 $(u_i, v_i)$ 的权值为 $w_i$。
图中有可能存在重边和自环。
如果$p = 1$，则输出一共两行
第一行：最短路径，从源点到终点依次输出所经过得节点；第二行：一个非负整数，表示点 $s$ 到点 $t$ 的最短路长度。
数据保证仅一条最短通路。
如果$p = 0$，则输出一行一个非负整数，表示点 $s$ 到点 $t$ 的最短路长度。
8 15 1 8
1
1 2 5
2 5 6
5 8 5
1 3 2
3 6 3
6 8 9
1 4 3
4 7 1
7 8 11
3 2 1
3 5 7
4 3 6
3 7 1
7 6 3
6 5 11 3 6 5 8
117 11 5 4
0
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 17请注意重边和自环的处理，不需要对最短路算法进行优化就可以通过本题。
经典图论问题，该题所有伪代码可以见算法导论或算法课 PPT。
老生常谈的使用Python提交时注意Python版本，例如Python3。
如果TLE的话，可以考虑：
计算到终点$t$就不需要继续往后计算了。
如果$p = 0$的话就不需要计算中间的路径了。