Problem
Bugün Aisne Kalesi, her biri 1'den n'ye kadar kendi benzersiz numarasına sahip n fırının katıldığı bir turta festivaline ev sahipliği yapıyor.
Bazı fırınlar birbirine iki yönlü yollarla bağlıdır, ancak öyle ki, i fırınından j fırınına yürümek mümkünse, aralarında tam olarak bir yol vardır.
En, i'inci fırında börek yerken A
i zevklerine kavuşur. Ve v ve u numaralı bazı fırınların arasından yol boyunca geçerse, turtaların lezzetli aroması C
v,u zevki getirir.
En, her fırına bir kereden fazla gitmek istemiyor (bazıları hiç gitmeyebilir), ancak festivalden en iyi şekilde yararlanmak istiyor.
Fırınlardan birinden başlayacak ve aralarından sadece mevcut yolları kullanarak geçecek.
En'in alabileceği maksimum olası zevki belirlemesine yardım edin.
Giriş:
İlk satır n (1
) sayısını içerir - fırın sayısı ve k sayısı - fırınlar arasındaki mevcut yolların sayısı.
İkinci satır n adet A
i (0 <= A
i <= 10000) içerir - i. fırında turta keyfi.
Ardından, her biri 3 sayı v, u, C (1 <= v, u
Çıktı:
Bir sayı yazdırın - mümkün olan maksimum memnuniyet.
Örnekler:
| Giriş |
Çıktı |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
Açıklamalar:
İlk örnekte, 1. fırından başlamanız (1 ikram), 1. ve 2. fırınlar arasındaki yol boyunca yürümeniz (1 ikram) ve 2. fırını (1 ikram) ziyaret etmeniz gerekiyor. Toplam zevk - 1+1+1 = 3.
İkinci örnekte 5. fırından başlamanız (10 zevk), 5. ve 4. fırınlar arasındaki yol boyunca yürümeniz (1 zevk), 4. fırını ziyaret etmeniz (6 zevk), 4. ve 2. fırın arasındaki yolu takip etmeniz gerekiyor. fırın (1 ikramlık), 2. fırını ziyaret edin (5 ikram), 2. ve 3. fırınlar arasındaki yol boyunca yürüyün (10 ikram), 3. fırını ziyaret edin (4 ikram). Toplam zevk - 10+1+6+1+5+10+4 = 37.