互帮助

题目描述

有$n$个小朋友，编号从$1\sim n$。

他们之间有些人相互认识。

现在他们遇到了一道题目，其中有些人会做，有些人不会做。

每对相互认识的人之间都有一个交流时间（单位：分钟）。

如果一个人会做这道题，他会教自己认识的且不会做这道题小朋友们做这道题，教题花费的时间是他和这个小朋友的交流时间。他可以同时和多个认识的小朋友们一起交流。

如果一个人学会了题目之后，他也立刻会去教自己认识的且不会做这道题的小朋友们。

请问要经过多少分钟所有的小朋友都能会这道题？

输入格式

第一行输入两个正整数$n,m$表示有$n$个小朋友，有$m$对人相互认识。

第二行一个长度为$n$的只包含'0'和'1'的字符串 $s$。'0'表示第$i$个小朋友不会这题，'1'表示第$i$个小朋友会这题。

接下来$m$行，每行三个整数$u,v,w$表示$u$和$v$之间的交流时间为$w$分钟。

输出格式

输出一个整数表示经过多少分钟之后所有的小朋友都会这题。

如果无论如何都不能够使所有的小朋友会这道题，输出"-1"(不含引号)。

样例 #1

样例输入 #1

5 5
10001
1 5 2
5 2 3
5 3 1
2 4 2
1 4 10

样例输出 #1

5

样例 #2

样例输入 #2

3 1
100
2 3 4

样例输出 #2

-1

提示

对于所有数据满足$1\le n\le 100,1\le m\le \min\left(\cfrac{n(n+1)}{2},1000\right),1\le u,v\le n,u\neq v,1\le w\le 100$。保证每对相互认识的人都不相同。

有$5\%$的数据满足字符串的字符均为'1'。

有$5\%$的数据满足字符串的字符均为'0'。

有$30\%$的数据满足$w$的值均为相同的值。

样例$1$： 第一个和第五个小朋友刚开始就会这题，一开始他们开始教自己认识且不会这题的小朋友。

$1$分钟过去后，$3$号小朋友学会了这题，但是他没有认识且不会这题的小朋友了。

$3$分钟过去后，$2$号小朋友学会了这题，他也开始教自己认识且不会这题的小朋友。

$5$分钟过去后，$4$号小朋友也学会了这题。（$2$号小朋友学会后教了他$2$分钟）

这时候所有的小朋友都会这道题了。

样例$2$：

$2,3$号小朋友一直都没法学会这题。