• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

همانطور که می‌دانید ماشین زمان اختراع شده و حتی آقابزرگ هم برای آزمایش از آن استفاده کرده است. هدف او رفتن به سال ۱۵۰۰ بوده ولی ظاهرا ماشین مشکلاتی داشته و او به زمانی دیگر رفته است. محققان اثبات کرده اند که از ابتدا تا نابودی سیاره‌ی زمین را می‌توان با استفاده از خاصیت «کیتی» $n$ نقطه بحرانی از زمین به $k$ عصر مختلف تقسیم کرد که باشماره‌های 1 تا $k$ شماره‌گذاری شده‌اند. به طور دقیقتر به هر عصر یه رشته‌ی $n$ بیتی اختصاص داده شده به طوری که اگر نقطه‌ی $i$ام در آن عصر خاصیت «کیتی» داشته باشد، بیت $i$ام آن یک است و در غیر این صورت برابر با صفر است (دانستن خاصیت یتی تأثیری بر حل سوال نخواهد داشت). رشته‌ی مربوط به هیچ دو عصری یکسان نیست.

آقا بزرگ می‌خواهد در سریع‌تری زمان ممکن بفهمد در کدام عصر قرار دارد. برای این کار او می‌تواند یکی از نقاط بحرانی زمین را انتخاب کند و در آن قرار بگیرد. سپس می‌تواند برای انتقال بین نقاط بحرانی از جاده‌های باستانی زمین استفاده کند. این جاده ها دو طرفه هستند و بین $n$ نقطه‌ی بحرانی ساخته شده‌اند و آقابزرگ می‌داند که برای عبور از هریک از جاده‌ها چقدر زمان نیاز دارد. آقابزرگ، در ره نقطه‌ی بحرانی می‌تواند خاصیت «کیتی» آن نقطه را بررسی کند. او بسیار باهوش است و در نتیجه در اولین لحظه‌ای که بتواند با توجه به خواص کیتی نقاط بحرانی عصر فعلی را تشخیص دهد، متوقف می‌شود و بلافاصله به سال ۱۵۰۰ می‌رود. آقا بزرگ بسیار عجله دارد و می‌خواهد هرچه سریع‌تر به سال ۱۵۰۰ برود. به همین دلیل، می‌خواهدبدانه مستقل از عسری که در آن است، حداکثر چقدر زمان لازم دارد تا بتواند به سال ۱۵۰۰ برود؟

ورودی

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

در سطر $i$ام از $k$ سطر بعدی، رشته‌ی $n$ بیتی متناظر با عصر $i$ام آمده است.

در هر یک از $m$ سطر بعدی، عدد $w, v ,u$ آمده است که وجود یک جاده‌ی باستانی بین دو نقطه‌ی بحرانی $u$ و $v$ است به طوری که طی کردن آن توسط آقابزرگ، $w$ ثانیه طول می‌کشد. $$1 \leq n,m \leq 1\ 000$$

$$1 \leq k \leq 11$$

$$1 \leq w \leq 100\ 000 , u \ne v , 1 \leq u,v \leq n$$

خروجی

در تنها سطر خروجی، پاسخ مسئله را چاپ کنید.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

5 4 6
0001
0000
0010
0100
1000
1 2 1
2 3 1
3 4 1
1 4 10
1 3 10
2 4 10

خروجی نمونه ۱

3

ورودی نمونه ۲

3 3 3
000
001
011
1 2 1
1 3 1
2 3 3

خروجی نمونه ۲

2

۲۵امین دوره المپیاد کامپیوتر - آزمون اول - ۱۳۹۴/۵/۳۱