Problem E
Viðnámsflækja

Image from commons.wikimedia.org

As per usual everything is in disarray at KFFÍ right before the contest. While others are just starting to turn up at Reykjavík University to prepare things Bjarki has already shown up and is crawling under the tables. When asked why he was doing that he said he was fixing the cables and connecting everything up correctly. However something seems to be amiss as the cables are heating up quite significantly. The problem is of course the resistance, higher resistance means more heat. While Bjarki crawls out from beneath the tables to take a break, could you figure out what the resistance between two points in the mess of cables is?

Input is given as a collection of points where cables meet along with the cables between these points. Each cable has some resistance $n \Omega $, where $\Omega $ is the unit Ohm. You will also be given the two points to measure the resistance between. Lucky for you some physics student left their notes behind in the room, so you have some information on how to calculate this.

Rule 1: If two points $x, y$ have two different cables going between them with resistances $n \Omega $ and $m \Omega $ they can be replaced with a single cable with resistance $1/(1/n+1/m) \Omega $.

Figure 1: Rule 1

Rule 2: Assume we have some point $x$ which is neither of the endpoints we are measuring the resistance between. Furthermore let us assume $x$ is connected to exactly two cables going to different points $a, b$, the cables having resistances $n \Omega $ and $m \Omega $. Then the point $x$ can be omitted and $a$ and $b$ instead be connected with a single cable of resistance $(n + m)\Omega $.

Figure 2: Rule 2

Rule 3: Assume we have some point $x$ which is neither of the endpoints we are measuring the resistance between. Furthermore let us assume $x$ is connected to exactly three cables going to different points $a, b, c$, the cables having resistances $n \Omega $, $m \Omega $ and $l \Omega $, in that order. Let $s = (nm + nl + ml)$. Then the point $x$ can be omitted and replaced with three cables, one from $a$ to $b$ with resistance $s/l \Omega $, one from $a$ to $c$ with resistance $s/m \Omega $ and one from $b$ to $c$ with resistance $s/n \Omega $. This change can also be done in reverse.

Figure 3: Rule 3

Input

The first line of the input contains two integers $2 \leq n \leq 100$ and $1 \leq m \leq 10^5$, the number of points and the number of cables. The next line contains two different integers $1 \leq s, t \leq n$, the two points that the resistance should be measured between. Finally there are $m$ lines, each with three integers $1 \leq a, b \leq n$ and $1 \leq x \leq 1000$. $a, b$ are different and denote the end points of the cable while $x \Omega $ is its resistance. There will always be some sequence of cables going from $s$ to $t$. If some cable is not part of any simple path from $s$ to $t$ it does not affect the resistance. A simple path is a sequence of cables taking you from $s$ to $t$ without repeated cables.

Output

It can be shown that the answer will always be an integer fraction. Let us say the result is $p/q$ where $p, q$ are coprime. Since $p, q$ could be very large you should print $pq^{-1} \pmod{10^9 + 7}$. This inverse is taken with respect to the modulus.

Scoring

Explanation of Sample Inputs

The first sample input is in group 1. The answer is $12/25$. $12 \cdot 25^{-1} \pmod{10^9 + 7}$ is $360\, 000\, 003$. This is because $360\, 000\, 003 \cdot 25 \equiv 12 \pmod{10^9 + 7}$. The numbers by the arrows in the image denote which rule was used.

Figure 4: Sample 1

The second sample input is in group 2. The arrow denoted by $0$ means we are removing cables that are not part of any simple path between the end points.

Figure 5: Sample 2

The third sample is in group 3. The answer is $20/11$. $20 \cdot 11^{-1} \pmod{10^9 + 7}$ is exactly $363\, 636\, 368$.

Figure 6: Sample 3

The fourth sample input is in group 4. The arrow denoted by $3’$ means we use rule $3$ in reverse. The result is $5/6$, $5 \cdot 6^{-1} \pmod{10^9+7}$ is $833\, 333\, 340$.

Figure 7: Sample 4

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

360000003

7 6
1 7
1 2 1
2 3 4
2 4 2
4 5 1
5 6 1
4 7 3

6

6 7
1 6
1 2 1
2 6 3
1 3 2
3 4 1
3 5 2
4 6 1
5 6 2

363636368

8 12
1 8
1 2 1
1 3 1
1 5 1
2 4 1
2 6 1
3 4 1
3 7 1
4 8 1
5 6 1
5 7 1
6 8 1
7 8 1

833333340