E. Exterior
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Examples
Input
4 4
6 2 1 5
1 2 1
2 3 6
1 3 8
3 4 2
Output
6
Input
5 4
12 23 34 45 56
1 2 1
2 3 1
3 4 1
4 5 1
Output
4
Input
6 7
8 5 1 7 8 6
2 3 1
2 5 1
3 5 4
2 6 3
4 5 17
3 4 10
5 6 2
Output
13