Make sure your graph is more than 1296 and try these

3
2
1 2 0
1 5 0
*
3
1 8 2 3 0
1 -5 0
2 25 0
*
2
1 8 2 22 3 -15 0
2 19 3 -50 0

ans = -20

===========================

4
2
1 2 0
1 5 0
*
4
1 8 2 3 0
1 -5 0
2 25 0
1 22 2 -3 0
*
3
1 8 2 22 3 -15 0
2 19 3 -50 0
4 -1 2 -5 0
*
4
1 -8 2 18 0
1 -5 0
2 -19 3 -22 0
1 12 0

ans= -39

==============================

2
2
1 2 0
1 5 0
*
4
1 8 2 3 0
1 -5 0
2 25 0
1 22 2 -3 0

ans = -3

==========================

4
2
1 2 0
1 5 0
*
4
1 81 2 23 0
1 56 0
2 25 0
1 22 2 -31 0
*
3
1 8 2 22 3 -15 0
2 19 3 -50 0
4 -1 2 -5 0
*
4
1  82 2 18 0
1  59 0
2  39 3 52 0
1 112 0

ans = -2