题目描述

王胖浩触电了！快来救他！

现在有 $m$ 条电线，$n$ 个交叉点。每条电线连接两个交叉点。电源在 $s$ 点，王胖浩在 $t$ 点。每条线段有硬度，宽度，危险程度。

求确定剪断那些电线，使得 $s$ 与 $t$ 不连通，且最小化要剪断的电线的硬度之和与宽度之和与危险程度之和的乘积。

请在 2s 以内出解，否则王胖浩就被电死了。

输入格式

本题有多组数据，以 EOF 结尾。

第一行 $4$ 个数 $n,m,s,t$，如题面所述。

接下来 $m$ 行，每行 $5$ 个数 $x_i,y_i,h_i,w_i,d_i$，分别表示第 $i$ 条电线连接的两个交叉点，硬度，宽度和危险程度。

输出格式

每组数据占一行输出，每行一个数 ans，表示最小的解。

4 4 1 4
1 2 1 1 1
1 3 1 2 1
3 4 2 1 1
2 4 2 2 2

12

数据范围与提示

对于 $100\%$ 的数据，$1\le n\le 50$，$1\le m\le 100$，$0\le h_i,w_i,d_i\le 10^4$，$s\ne t$，数据组数不会超过 $2$ 组。

题目来源

2014 年国家集训队十五人互测