题目描述

一侧的交通道路连接了许多城市。城市从 $1$ 到 $n$ 编号，其中 $n$ 是城市的数量。在奇数天，车辆按照交通指示的方向行驶，在偶数天，则沿相反的方向行驶。两个城市之间的道路长度用一个整数值来衡量——从一个城市到另一个城市的旅程的持续时间（以小时为单位），它与方向无关。

编写一个程序来查找从城市 A 到城市 B 的路线，以便尽可能快地到达城市 B。

旅程的第一天是奇数天。一天之内的旅程不能超过十二个小时。晚上必须在一个城市度过。行程可能会在第二天继续。

输入格式

第一行包含两个整数为 A 和 B 城市的编号，第二行包含两个整数为城市总数和道路总数 $k$。剩下的 $k$ 行中有每条道路的信息，每行包含三个整数——道路连接的两个城市的编号以及以小时表示的城市之间旅程的持续时间。道路的方向是从第一城到第二城。

输出格式

每条中间路径输出一行。每行应该有四个整数——出发城市标号、到达城市编号、日期和道路长度。

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

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 < n \le 100$，$1 \le k \le 1000$。

样例说明

分值说明

本题分值按 BOI 原题设置，满分 $35$ 。

题目说明

来源于 Baltic Olympiad in Informatics 1996 的 Day 2:A FAST JOURNEY。
由 @求学的企鹅 翻译整理。