Salam, Piroq!

Picceriya Pizazz öz alıcılarına imkan daxilində daha tez pizza çatdıra bilməsi ilə fəxr edir. Bədbəxtçilikdən çatdırma üçün yalnız bir sürücü tutmaq olar. Çatdırmadan əvvəl o müəyyən sayda ($1$-dən $20$-a qədər) sifariş gəlməsini gözləyir. Sürücü bütün sifarişlərin çatdırılması üçün, hətta eyni bir yerə bir neçə dəfə getmək tələb olunsa da, ən qısa yolu seçməyə üstünlük verir. Çatdırılma sonunda sürücü cari yerinə, yəni picceriyaya qayıtmalıdır. Sizə belə marşrutu seçməyə imkan verən proqram yazmaq lazımdır.

Giriş verilənləri

İlk sətirdə sifarişlərin $n(1\le n\le 20)$ sayı verilir. Sonra hər biri $n+1$ tam ədəd ehtiva edən $n+1$ sətir verilir. Bu ədədlər picceriya (onun nömrəsi $0$-dır) və sifarişlərin verildiyi $n$ yer (onlar $1$-dən $n$-ə qədər nömrələnir). $i$ sətrinin $j$-ci qiyməti $i$-yerindən $j$ yerinə yol boyunca başqa yerlərə baş çəkmədən birbaşa getmə vaxtına işarə edir. Qeyd edək ki, yollarda tıxacların və işıqforların olması səbəbindən $i$ və $j$ yerləri arasında birbaşa gediş daha tez olmaya bilər. Gediş vaxtı simmetrik deyil. Yəni, $i$-dən $j$-yə birbaşa gedişi vaxtı $j$-dən $i$-yə gedış vaxtı ilə eyni olmaya bilər.

Çıxış verilənləri

Pizzanı bütün sifarişçilərə çatdırmaq və geriyə qayıtmaq üçün lazım gələn minimal vaxtı verməli.

Nümunələr