### 问题描述 有一个有 $n$ 个节点和 $m$ 个边的有向无环图 $G$，边有边权。有两个机器人，第一个机器人位于节点 $a$，第二个机器人位于节点 $b$。你需要让第一个机器人移动到节点 $c$，让第二个机器人移动到节点 $d$。两个机器人可以同时位于同一个节点。 你可以执行以下三种操作： 1. 选择第一个机器人所在的节点的一个出边，让第一个机器人沿着这条边移动。此操作的花费为这条边的边权。 2. 选择第二个机器人所在的节点的一个出边，让第二个机器人沿着这条边移动。此操作的花费为这条边的边权。 3. 分别选择第一个机器人和第二个机器人所在的节点的各一个出边，让两个机器人分别沿着两条出边移动。此操作的花费为选择的两条边的边权的最大值。特别的，当两个机器人位于同一个节点时，可以执行此操作，但必须选择两个不同的出边。 求让两个机器人分别到达它们的目标节点需要的最小花费。如果不可能让两个机器人都到达它们的目标节点，输出 $-1$。注意必须让两个机器人到达各自的目标节点。让第一个机器人到达节点 $d$，第二个机器人到达节点 $c$ 不被认为满足条件。 ### 输入格式 输入第一行包含六个正整数 $n,m,a,b,c,d$，分别表示节点的总数，边的总数，第一个机器人的初始节点，第二个机器人的初始节点，第一个机器人的目标节点，第二个机器人的目标节点。 接下来 $m$ 行，每行包含三个正整数 $u_i,v_i,w_i$，表示每条边的起点，终点和边权。 ### 输出格式 输出让两个机器人分别到达它们的目标节点需要的最小花费。如果不可能让两个机器人都到达它们的目标节点，输出 $-1$。 ### 样例输入 ```text 7 8 1 1 6 7 1 2 4 2 3 1 3 4 4 1 5 5 5 4 5 1 4 7 4 6 100 4 7 100 ``` ### 样例输出 ```text 111 ``` ### 说明 有向无环图 $G$ 有 $7$ 个节点，$8$ 个边。两个机器人初始都位于节点 $1$，第一个机器人需要前往节点 $6$，第二个机器人要前往节点 $7$。 一种让花费最小化的方法为： 第一步，使用操作 $3$，让第一个机器人沿第 $1$ 条边前往节点 $2$，让第二个机器人沿第 $4$ 条边前往节点 $5$。此操作消耗为 $5$。 第二步，使用操作 $1$，让第一个机器人沿第 $2$ 条边前往节点 $3$。此操作消耗为 $1$。 第三步，使用操作 $3$，让第一个机器人沿第 $3$ 条边前往节点 $4$，让第二个机器人沿第 $5$ 条边前往节点 $4$。此操作消耗为 $5$。 第四步，使用操作 $3$，让第一个机器人沿第 $7$ 条边前往节点 $6$，让第二个机器人沿第 $8$ 条边前往节点 $7$。此操作消耗为 $100$。 总消耗为 $111$。可以证明不存在让总消耗更低的操作方式。 ### 评测数据规模 对于 $20$% 的评测数据，$2\leq n \leq 20,2\leq m \leq 40$。 对于 $100$% 的评测数据，$2\leq n \leq 1000,2\leq m \leq \min(\frac{n \cdot (n-1)}{2},2000),1\leq u_i，v_i \leq n,u_i \neq v_,1\leq w_i \leq 10^9$。保证输入的边没有重边，且构成一个有向无环图。