$n$ شهر با شماره‌های ۱ تا $n$ با تعدادی جاده‌ی یک‌طرفه به هم مربوط‌اند $(n\leq 100)$. در روزهای فرد وسایط نقلیه در جهت داده شده حرکت می‌کنند و در روزهای زوج، جهت تمام جاده‌ها برعکس می‌شود. زمان لازم برای طی مسافت شهر به شهر (مستقل از جهت حرکت) بر حسب ساعت داده شده. برنامه‌ای بنویسید که سریع‌ترین مسیر از شهر $A$ به شهر $B$ را پیدا کند. روز شروع حرکت (روز ۱) روز فرد است. در یک روز حداکثر ۱۲ ساعت می‌توان حرکت کرد و شب‌ها را باید در یکی از شهرها استراحت نمود.

در سطر اول فایل ورودی شماره‌ی شهرهای $A$ و $B$ و در سطر دوم، $n$ (تعداد شهرها) و $k$ (تعداد جاده‌ها) قرار دارد.

در هر یک از $k$ سطر بعدی ۳ عدد صحیح نوشته شده است. دو عدد اول شماره‌ی دو شهر مربوط به آن جاده و عدد سوم زمان لازم برای طی فاصله بین آن دو است. جهت حرکت در روزهای فرد از شهر اول به شهر دوم است.

در هر سطر از فایل خروجی ۳ عدد که به ترتیب شماره‌ی شهر مبدا، شماره‌ی شهر مقصد و روز حرکت بین دو شهر است.

• سوال بعد
• سوال قبل