Description

A one-way road network connects many cities. The cities are numbered from $1$ to $n$, where $n$ is the number of cities. On odd days, vehicles travel in the direction indicated by the traffic signs; on even days, they travel in the opposite direction. The length of a road between two cities is measured by an integer value—the duration (in hours) of traveling from one city to the other—and it does not depend on the direction.

Write a program to find a route from city A to city B so that city B is reached as fast as possible.

The first day of the journey is an odd day. The travel time within a single day cannot exceed twelve hours. At night, you must stay in a city. The trip may continue on the next day.

Input Format

The first line contains two integers, the indices of cities A and B. The second line contains two integers: the total number of cities and the total number of roads $k$. The remaining $k$ lines each describe one road. Each line contains three integers: the indices of the two cities connected by the road, and the travel time between the cities in hours. The direction of the road is from the first city to the second city.

Output Format

Output one line for each segment of the route. Each line should contain four integers: the departure city index, the arrival city index, the day number, and the road length.

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

1 5 1 10
5 4 1 1
4 3 3 4

Hint

Constraints

For $100 \%$ of the testdata, $1 < n \le 100$, $1 \le k \le 1000$.

Sample Explanation

Scoring

The score of this problem follows the original BOI settings, with a full score of $35$.

Notes

From Baltic Olympiad in Informatics 1996: Day 2:A FAST JOURNEY.
Translated and整理 (zhengli, compiled) by @求学的企鹅.

Translated by ChatGPT 5