409213: GYM103462 E Eaom and Longzhu

Long long ago,as the legend said,whoever collect $$$7$$$ kind of longzhu can summon a Dragon and Dragon will makes your dreams come true.

Currently, Baom is trapped in a maze out of the world. Baom is at room $$$1$$$ and the export is at room $$$n$$$. He surprisely find that there are longzhus in each room in the maze. Baom decide to escape the maze and collect enough longzhu to make a wish.

Unfortunately, he could collect excatly one longzhu each time he get into a room.

Forunately, the room is connected by some portals, Baom can transmit himself between portals which cost energies. And longzhu is so magical that can recover Baom $$$\frac{x_{ij}w}{10}$$$ energies where $$$i$$$ is the last kinds of longzhu you had collected, $$$j$$$ is the current longzhu you just collcet and $$$w$$$ is the energies you had just cost during the transmission.

Baom hope to escape the maze and collected all kinds of longzhu with minimum energies costs.Can you help him?

Note that Baom can collected the same kind of longzhu at different rooms or collect different kind of longzhu at the same room if Baom come into it again.

The number of longzhu is infinite in each room.

The first line contains integers $$$n,m (1 \leq n \leq 5\cdot 10^2,1 \leq m \leq \frac{n(n-1)}{2})$$$—number of rooms and portals.

Next $$$7$$$ lines each line contains $$$7$$$ integers $$$x_{ij} (0\leq x_{ij}\leq 10)$$$–the number described above.

Next $$$m$$$ lines each line contains $$$3$$$ integers $$$u,v,w (1\leq u,v\leq n,1\leq w\leq 10^5 \; and \; w \equiv 0\bmod 10)$$$.

Print a single integer —- the minimum cost of energies if exist else $$$-1$$$.

3 3
0 3 9 0 6 8 1
5 0 1 5 3 8 8
7 4 5 2 5 6 9
3 0 9 7 0 1 8
6 3 8 7 0 4 9
2 9 6 6 8 3 3
4 1 2 7 7 8 3
2 1 40
1 3 60
2 3 40

44