# Problem K

Kaguya Wa Saketakunai

The *Shinomiya* corporation is Japan’s
biggest family-owned conglomerate, with a portfolio of multiple
businesses in railway, trade and retail. With a family of such
high esteem, it is important to maintain their status and
image, paramount to stereotypical Asian culture.

The family has a daughter by the name of *Kaguya*, who is in love with and currently dating
her student council president *Miyuki
Shirogane*.

However, there is a big issue. *Miyuki’s* family is not very well to do and his
father works multiple jobs to make ends meet. Upon the
*Shinomiya* family finding out about this,
they expressed great displeasure over *Kaguya* and *Miyuki*’s
relationship. In their eyes, *Kaguya*
should marry someone of similar status and not lower herself,
indirectly destroying the family’s reputation.

Much to the annoyance of *Kaguya’s*
parents, the couple want to stay together due to their undying
love for one another. Henceforth, *Kaguya’s* parents have devised a scheme to prevent
*Miyuki* from visiting *Kaguya*.

It is a well known fact that the *Shinomiya* family’s house is located on an
extremely large plot of land in *Tokyo*.
More formally, it is modelled as a plot of land with
$N$ junctions and
$E$ roads. Since the
entire plot of land is owned by the family, it is guaranteed
that there is a path between any $2$ junctions and there is at most one
road between $2$ adjacent
junctions.

The $i$th road is
$w_{i}$ units long, for
every $i = 1 \dots E$.
Knowing that *Miyuki* frequently commutes
on his bicycle and will take a significant amount of energy to
travel between $2$
locations, *Kaguya’s* family’s have
devised a plan. They will hire a contractor to increase the
length of some subset of roads. The family wants to increase
the length of a subset of roads in such a way that **increases** the total amount of time Miyuki will
take to travel from the entrance to the actual family house. In
a single operation, the contractor can increase the duration
needed to travel through any road by exactly $1$ unit of time.

Furthermore, *Miyuki* will always take
a route from the entrance to the family’s house that can be
covered in the least amount of time possible.

Being business-minded people, the family are willing to pay
you a fortune for you to devise a scheme that uses the
**minimum** number of operations to
increase the time that *Miyuki* will take
to travel from the entrance of the compound to *Shinomiya’s* family’s house. Can you help
them?

## Input

The first line contains $4$ integers, $1 \le N \le 2000$, the number of
junctions, $1 \le E \le 40\,
000$, the number of roads, and $1 \leq s, d \leq N$, ($s \neq d$), the junctions where the
entrance to the compound, and the *Shinomiya* house, is located, respectively.

The next $E$ lines contain the roads, each on one line. Each road is given in the form $u\, v\, w$ where $u,v$ are the $2$ endpoints of an road ($1 \leq u,v \leq N$) and $w$ is the time it takes to traverse the road ($1 \le w \le 10^{9}$). The road can be traversed in both directions.

## Output

On $1$ line, print the minimum number of operations required.

For every road in which the operation is applied at least once, print it on a single line in the form of $u\, v\, f$ where $u$ and $v$ are the endpoints of the edge and $f$ is the number of times the operation is applied.

Each road should be included in the output at most once. Roads where the operation is applied $0$ times need not be printed.

If there are multiple solutions, print any one of them.

Sample Input 1 | Sample Output 1 |
---|---|

8 8 7 1 6 7 1 8 4 2 2 6 2 1 7 9 2 5 6 8 5 4 3 2 5 5 4 6 |
1 7 1 1 |

Sample Input 2 | Sample Output 2 |
---|---|

2 1 1 2 2 1 6 |
1 1 2 1 |

Sample Input 3 | Sample Output 3 |
---|---|

8 10 8 2 1 6 8 2 4 3 7 8 8 4 5 7 3 1 10 1 4 9 2 8 4 3 6 9 6 8 1 3 4 9 |
1 8 2 1 |

Sample Input 4 | Sample Output 4 |
---|---|

5 6 1 5 1 2 1 1 3 3 2 3 1 2 5 3 3 5 1 4 5 1 |
1 1 2 1 |

Sample Input 5 | Sample Output 5 |
---|---|

5 6 1 5 1 2 1 1 3 2 1 4 1 2 3 1 2 5 2 3 5 1 |
2 1 2 1 1 3 1 |