同图的建设费与通行费

难度：T2

【知识点：生成树与最短路辨析】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

同一张无向图有两种独立任务：用一部分边连通全图，求最低建设费；在原图中从 $s$ 到 $t$ ，求最短通行距离。通行不限制在选出的生成树上。

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$ ； $m$ 为随后给出的带权边条数。每条带权边独占一行，依次为 $u,v,w$ ，表示从 $u$ 到 $v$ 的边及权值 $w$ ；无向边可双向通行，有向边只能从 $u$ 到 $v$ 通行。

输入 $n$ 、 $m$ 、 $s$ 、 $t$ 及 $m$ 条无向非负权边。同一权值分别用于全网建设费用和通行距离。

生成树是选取原图中的一部分边，使所有顶点连通且不形成环；费用为选中边的权值之和。最小生成树是在所有生成树中总费用最小的一个。只有一个顶点时，不选边即可形成生成树，费用为 $0$ 。

全图不能连通输出IMPOSSIBLE，否则输出最小生成树总费用及原图 $s$ 到 $t$ 最短距离。

$1\le n\le 500$ ， $0\le m\le 200000$ ， $0\le w\le 10^9$ ，编号在 $1$ .. $n$ 。

4 3