Problem G: DSAA Path

Problem G: DSAA Path

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1059  Solved: 146
[Submit][Status][Web Board]

Description

Input

Output

Sample Input

1
4 5 1
1 2 1
1 3 2
1 4 3
3 4 2
2 3 2
2

Sample Output

5

HINT

[Submit][Status]