H. Optimization for UltraNet
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Examples
Input
3 3
1 2 5
1 3 6
2 3 8
Output
20
Input
5 7
1 2 6
1 3 10
1 4 12
2 4 8
2 5 3
3 4 4
4 5 2
Output
44
Input
5 5
2 5 1
1 2 2
2 3 4
1 3 5
2 4 6
Output
24