题目描述

有一个图，$N$ 个点 $M$ 条边。

求出点 $S$ 到点 $T$ 的 $K$ 短路。

2 2
1 2 5
2 1 4
1 2 2

14

数据范围

$1\leq N\leq1000, 0 \leq M \leq100000$。

$1 \leq S, T\leq N, 1\leq K \leq1000$。

$1 \leq A, B \leq N, 1 \leq T \leq 100$。

具体可看英文题面。