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.

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

2 1 1 2
2 1 6

1
1 2 1

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

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

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