* $1 ≤ N ≤ 250$
* $1 ≤ M ≤ 1000$
* Se garantează că graful aciclic si exista cel putin un drum de la $1$ la $N$.

* $0$ $≤ A[i][j] ≤ 10^9$
* A[i][j-1] ≤ A[i][j]
* Muchiile au lungimea initiala ≤ $10^9$
* Pot exista mai multe muchii între aceeaşi pereche de noduri

h2. Subtaskuri

h2. Exemplu
table(example). |_. curcani.in |_. curcani.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|5 7 1
1 2 41
1 5 45
2 3 1
2 4 2
3 5 3
4 5 2
4 5 2
1
1
3
3
4
2
4
| 2
|
| 6 13 2
1 3 103
1 3 104
1 5 113
3 2 7
2 4 14
2 5 4
2 6 20
5 6 18
5 4 12
5 4 11
4 6 7
4 6 7
4 6 6
12 35
12 35
12 34
11 32
11 32
11 33
11 33
12 36
11 32
12 35
12 36
12 36
11 33
| 45

|
h3. Explicaţie

...

Pentru primul exemplu trebuie incrementate primele 2 muchii cu cate o unitate.
Pentru al doilea exemplu va trebui sa ne credeţi pe cuvânt.

== include(page="template/taskfooter" task_id="curcani") ==