| Codeforces Round 234 (Div. 2) |
|---|
| Закончено |
Дима стал заниматься биологией бактерий, в результате своих опытов он вывел k видов бактерий. Всего сейчас в его лаборатории содержится n бактерий, причем количество бактерий вида i равно ci. Для удобства будем считать, что все бактерии пронумерованы от 1 до n. При этом бактерии вида ci имеют номера от 
до 
.
С помощью специального оборудования Дима может передавать энергию между некоторыми бактериями. Конечно, пользование таким оборудованием не бесплатно. Дима знает m способов передачи энергии с помощью оборудования. Способ с номером i характеризуется тремя целыми числами vi, ui, xi и позволяет за xi долларов передавать энергию от бактерии с номером ui к бактерии с номером vi или наоборот.
Начальник Димы (Инна) считает, что распределение на виды устроено правильным образом, если существует способ (возможно, использовав оборудование несколько раз) передать энергию от любой бактерии определенного вида другой бактерии этого же вида бесплатно (для любых двух бактерий одного и того же вида).
Поскольку в таком случае стоимость передачи энергии от любой бактерии к любой другой зависит лишь только от видов этих двух бактерий, помогите Инне определить: образуют ли выведенные Димой бактерии устроенное правильным образом распределение на виды? И если образуют, выведите матрицу d размера k × k. Ячейка d[i][j] этой матрицы должна обозначать стоимость передачи энергии от бактерии вида i к бактерии вида j.
В первой строке записаны три целых числа n, m, k (1 ≤ n ≤ 105; 0 ≤ m ≤ 105; 1 ≤ k ≤ 500). В следующей строке записаны k целых чисел c1, c2, ..., ck (1 ≤ ci ≤ n). В каждой из следующих m строк записано три целых числа ui, vi, xi (1 ≤ ui, vi ≤ n; 0 ≤ xi ≤ 104; ui ≠ vi). Гарантируется, что 
.
Если распределение Димы устроено правильным образом, выведите строку «Yes», а затем k строк: в i-й строке выведите целые числа d[i][1], d[i][2], ..., d[i][k] (d[i][i] = 0). Если нельзя передать энергию бактерии типа j от бактерии типа i соответствующее значение d[i][j] должно быть равно -1. Если распределение Димы устроено неправильным образом, выведите «No».
4 4 2
1 3
2 3 0
3 4 0
2 4 1
2 1 2
Yes
0 2
2 0
3 1 2
2 1
1 2 0
Yes
0 -1
-1 0
3 2 2
2 1
1 2 0
2 3 1
Yes
0 1
1 0
3 0 2
1 2
No
