SP4227 MSE06I - "Shortest" pair of paths

有一张 $n$ 个点，$m$ 条边的有向图，其中点编号为 $0$ 到 $n-1$，边有边权。 你要在这个图上找到两条从 $0$ 到 $n-1$ 的路径，使得这两条路径除了 $0$ 和 $n-1$ 这两个点外，其余点均不相交。请你输出这两条路径的最小边权和。

**输入包含多组数据。** 对于每组数据，首先输入两个非负整数 $n$ 和 $m$，分别表示图的点数和边数。 接下来 $m$ 行，每行三个整数 $u, v, c$，表示一条边权为 $c$ 的有向边 $(u, v)$。 当 $n$ 和 $m$ 均为 $0$ 时，表示输入结束，此时你不需要再输出任何信息。

对于每组数据，首先输出 `Instance #` $+$ 当前数据组数 $+$ `: `。 接下来，如果该组数据无合法方案，输出 `Not possible`；否则输出一个整数，表示你的答案。 注意，同一组数据中，这两条信息位于同一行。你可以参考样例的输入输出。 ### 输入输出样例 输入： ```text 2 1 0 1 20 2 3 0 1 20 0 1 20 1 0 10 4 6 0 1 22 1 3 11 0 2 14 2 3 26 0 3 43 0 3 58 0 0 ``` 输出： ```text Instance #1: Not possible Instance #2: 40 Instance #3: 73 ```

对于所有数据，保证 $0 \leq u, v, < n \leq 20, m \leq 200$，使用 `int` 可以通过本题数据。