两个出发站

难度：T2

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

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

题目描述

给出有向图和两个出发站 $s,t$。对每个目标点，可以任选一个出发站，求最短到达距离。每个目标独立选择出发站。

输入格式

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

输入$n$、$m$、$s$、$t$及$m$条有向非负权边。每个点可从$s$或$t$任一站出发。

输出格式

按编号输出到各点的最短到达距离；两个源都不可达输出-$1$。

数据范围

$1\le n\le 100000$，$0\le m\le 200000$，$0\le w\le 10^9$。

样例输入

2 1 1 2
1 2 2

样例输出

0 0