Recently Syrjälä's network collapsed, and now it's being rebuilt. Uolevi wants to know the earliest moment when he can play an online game. Given information about when the connections between computers are built, and the times required for a signal to go through particular connections, Uolevi wants to know the earliest moment when his ping (the lowest possible time required for a signal to go from Uolevi's computer to the game server through connections) is low enough.
The computers are numbered $1, 2, \ldots, n$. Uolevi's computer is number $1$ and the game server is number $n$. Initially there are no connections between the computers.
Input
The first line of input contains three integers, $n$, $q$ and $p$, the number of computers, the number of updates and the highest ping which is low enough. Then follows $q$ lines containing three integers each, $u_i$, $v_i$ and $d_i$ meaning that at time $i$ a bidirectional connection between computers $u_i$ and $v_i$ is built. $d_i$ is time required for a signal to go through the connection.
Output
Output a single integer, the lowest $i$ such that after first $i$ updates Uolevi can play the game with low enough ping. If Uolevi can never play the game with low enough ping, output
QAQ
.
Constraints
- $2 \le n \le 10^5$
- $0 \le q \le 10^5$
- $1 \le p \le 10^9$
- $1 \le u_i, v_i \le n$
- $1 \le d_i \le 10^9$
Examples
Input:
4 5 4
1 4 5
2 1 1
4 3 2
1 3 2
2 4 1
Output:
4
Input:
4 3 4
1 3 2
3 4 3
2 4 1
Output:
QAQ